Created
February 4, 2020 21:37
-
-
Save JessicaGreben/24162e7719872a3faa76e94eecce3d46 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
// stringMatch returns a list of indexes of the starting positions of the | |
// matching substr, does not count overlapping matches. | |
// worst case runtime: len(str) * len(substr) | |
// pathological inputs would be a substr that doesn't matches but has many similar chars | |
// so that for every char in str we would iterate thru all chars in the substr | |
// ex: aaaaaaaaa, aaad | |
// typical performance len(str) plus however many occurrences of the matching first chars of substr | |
func bruteStringMatch(str, substr string) []int { | |
if len(substr) > len(str) { | |
return []int{} | |
} | |
if str == "" || substr == "" { | |
return []int{} | |
} | |
var result []int | |
// i is pointer to current position in str | |
// j is pointer to current position in substr | |
var i, j int | |
Outer: | |
for i < len(str) { | |
start := i | |
// iterate over all chars in substr and see if it matches the char in str | |
for j = 0; j < len(substr); j++ { | |
// if the chars don't match or we are past the end of str | |
// then continue on and evaluate the next char in str | |
if i+j >= len(str) || string(substr[j]) != string(str[i+j]) { | |
i++ | |
continue Outer | |
} | |
} | |
// if all the chars in substr have successfully been evaluated | |
// then we found a match. Add the start index of the match to results. | |
result = append(result, start) | |
i += j | |
} | |
return result | |
} | |
// stringMatch returns a list of indexes that are the starting positions of the | |
// matching substr, does not count overlapping matches. | |
// run time: len(str) | |
func stringMatch(str, substr string) []int { | |
if len(substr) > len(str) { | |
return []int{} | |
} | |
if str == "" || substr == "" { | |
return []int{} | |
} | |
var result []int | |
// j is pointer to current position in substr | |
var j int | |
// i is pointer to current position in str | |
for i := 0; i < len(str); i++ { | |
// if the current char of the str and substr don't match, | |
// then reset the pointer j to the beginning of the substr | |
if string(str[i]) != string(substr[j]) { | |
j = 0 | |
} | |
// if the current char of the str and substr do match, then | |
// move the pointers i and j a single position forward and repeat | |
if string(str[i]) == string(substr[j]) { | |
j++ | |
if j == len(substr) { | |
substrStartIndex := i - len(substr) + 1 | |
result = append(result, substrStartIndex) | |
j = 0 | |
} | |
} | |
} | |
return result | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import "testing" | |
var testCases = []struct { | |
name string | |
str string | |
substr string | |
expected []int | |
}{ | |
{"1", "abcdbcdf", "bcd", []int{1, 4}}, | |
{"2", "a", "bcd", []int{}}, | |
{"3", "abc", "", []int{}}, | |
{"4", "afcdab", "cdf", []int{}}, | |
{"5", "Welchome Home Homey!", "Home", []int{9, 14}}, | |
{"6", "t o to to", "to", []int{4, 7}}, | |
{"7", "abcdbbbcdf", "bcd", []int{1, 6}}, | |
{"8", "aaa", "aa", []int{0}}, | |
{"9", "aaaaaaaaaaa", "aa", []int{0, 2, 4, 6, 8}}, | |
{"10", "abcdabcd", "abcf", []int{}}, | |
{"11", "aaaaaaaaaaa", "aaaad", []int{}}, | |
} | |
func TestBruteStringMatch(t *testing.T) { | |
for _, tc := range testCases { | |
t.Run(tc.name, func(t *testing.T) { | |
actual := bruteStringMatch(tc.str, tc.substr) | |
if len(actual) != len(tc.expected) { | |
t.Fatalf("expected: %#v\n, actual: %#v\n", tc.expected, actual) | |
} | |
for i := 0; i < len(actual); i++ { | |
if actual[i] != tc.expected[i] { | |
t.Fatalf("expected: %#v\n, actual: %#v\n", tc.expected, actual) | |
} | |
} | |
}) | |
} | |
} | |
func TestStringMatch(t *testing.T) { | |
for _, tc := range testCases { | |
t.Run(tc.name, func(t *testing.T) { | |
actual := stringMatch(tc.str, tc.substr) | |
if len(actual) != len(tc.expected) { | |
t.Fatalf("expected: %#v\n, actual: %#v\n", tc.expected, actual) | |
} | |
for i := 0; i < len(actual); i++ { | |
if actual[i] != tc.expected[i] { | |
t.Fatalf("expected: %#v\n, actual: %#v\n", tc.expected, actual) | |
} | |
} | |
}) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment