Here attached is my python Solution using KMP Algorithm.
The main idea is that we use the pattern inside the Pattern String, so that once we encounter a 'miss match', we can skip several bits to shorten the searching range. In Brute-Force algorithm, each time we will just switch to the next bit and start to compare from the very beginning.
It consists of two parts:
Given a Pattern String "abdyab", we can get next = [-1, 0, 0, 0, 0, 1];
Let me show you a simple way to get next Array:
Pattern: "a b d y a b"
First: "0 0 0 0 1 2"
SubString that begins from the beginning to 'a' has no match of prefix and suffix, so we get 0;
Same as 'b' , 'd', y', till 'a'.
Now you can see the first 'a' (prefix) matches this 'a'(suffix), and the matched length is 1, So we get 1;
You can go all the way to the end.
Then, do a little trick: Right shift by one bit and put '-1' on the first element.
Thus, you got '-1, 0, 0, 0, 0, 1'
Start searching using the principle shown in the main idea.
Code and have fun:)
class Solution(object): def strStr(self, haystack, needle): if not needle: return 0 length_hay = len(haystack) length_needle = len(needle) next = self.getNext(needle) i = 0 j = 0 while i < length_hay: if j == -1 or needle[j] == haystack[i]: j += 1 i += 1 if j == length_needle: return i - j else: j = next[j] return -1 def getNext(self, needle): next =  next.append(-1) length = len(needle) j = 0 k = -1 while j < length - 1: if k == -1 or needle[j] == needle[k]: j += 1 k += 1 next.append(k) else: k = next[k] return next