stringmatch.go

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
}

stringmatch_test.go

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)
				}
			}
		})
	}
}