404

That’s, unfortunately, an error.

It says that we can’t currently give you what you’re looking for…

However, here’s an algorithm by Knuth, Morris and Pratt which can find you a needle in a haystack.

Even better, it will do that in O(n) time!

func search(needle, haystack []byte) int {
	dfa := make([][]byte, 256)
	for i := range dfa {
		dfa[i] = make([]byte, len(needle))
	}

	dfa[needle[0]][0] = 1

	for x, i := 0, 1; i < len(needle); i++ {
		for c := 0; c < 256; c++ {
			dfa[c][i] = dfa[c][x]
		}

		dfa[needle[i]][i] = i + 1
		x = dfa[needle[i]][x]
	}

	s, i := 0, 0
	for ; s < len(needle) && i < len(haystack); i++ {
		s = dfa[haystack[i]][s]
	}

	if s == len(needle) {
		return i - len(needle)
	}

	return len(haystack)
}