Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 276
Good morning! Here's your coding interview problem for today.

This problem was asked by Dropbox.

Implement an efficient string matching algorithm.

That is, given a string of length N and a pattern of length k, write a program that searches for the pattern in the string with less than O(N * k) worst-case time complexity.

If the pattern is found, return the start index of its location. If not, return False.

Pull request description:
Day276
Resolves #561.

Patch:
diff --git a/README.md b/README.md
index 951ef4d..5cacecd 100644
--- a/README.md
+++ b/README.md
@@ -287,6 +287,7 @@ problems from
 * [Day 273](https://github.com/vaskoz/dailycodingproblem-go/issues/556)
 * [Day 274](https://github.com/vaskoz/dailycodingproblem-go/issues/559)
 * [Day 275](https://github.com/vaskoz/dailycodingproblem-go/issues/560)
+* [Day 276](https://github.com/vaskoz/dailycodingproblem-go/issues/561)
 * [Day 277](https://github.com/vaskoz/dailycodingproblem-go/issues/563)
 * [Day 278](https://github.com/vaskoz/dailycodingproblem-go/issues/565)
 * [Day 279](https://github.com/vaskoz/dailycodingproblem-go/issues/566)
diff --git a/day276/problem.go b/day276/problem.go
new file mode 100644
index 0000000..b254895
--- /dev/null
+++ b/day276/problem.go
@@ -0,0 +1,48 @@
+package day276
+
+// StringMatchKMP is an implementation of
+// https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
+// NOTE: only returns the index of the first occurrence. If not found, returns -1.
+// WARNING: only works on ascii characters.
+func StringMatchKMP(input, substr string) int {
+	var i, j int
+	table := buildTable(substr)
+	for i < len(input) {
+		if substr[j] == input[i] {
+			i++
+			j++
+		}
+		if j == len(substr) {
+			return i - j
+		}
+		if i < len(input) && substr[j] != input[i] {
+			if j != 0 {
+				j = table[j-1]
+			} else {
+				i++
+			}
+		}
+	}
+	return -1
+}
+
+func buildTable(substr string) []int {
+	table := make([]int, len(substr))
+	i := 1
+	last := 0
+	for i < len(table) {
+		if substr[i] == substr[last] {
+			last++
+			table[i] = last
+			i++
+		} else {
+			if last != 0 {
+				last = table[last-1]
+			} else {
+				table[i] = 0
+				i++
+			}
+		}
+	}
+	return table
+}


Test patch:
diff --git a/day276/problem_test.go b/day276/problem_test.go
new file mode 100644
index 0000000..86246c9
--- /dev/null
+++ b/day276/problem_test.go
@@ -0,0 +1,33 @@
+package day276
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	input, substr string
+	expected      int
+}{
+	{"hello world!", "wor", 6},
+	{"hello world!", "buddy", -1},
+	{"hello world!", "hello", 0},
+	{"hello world!", "ll", 2},
+	{"hello world!", "llo w", 2},
+	{"hello world!", "ld", 9},
+}
+
+func TestStringMatchKMP(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := StringMatchKMP(tc.input, tc.substr); result != tc.expected {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkStringMatchKMP(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			StringMatchKMP(tc.input, tc.substr)
+		}
+	}
+}