# The Sunday Algorithm, better than BM and KMP.

• Pass the test with 50ms(Python), Fast than BM(60ms) and KMP(200ms).

it is simaliry with BM, but use the next (after the last) charcter (BM use the unmatch charcter ) to get the next i.

``````def getRight(self,str):
n = len(str)
if n <= 0:
return []
right = [ -1 for i in range(256)]
for i,c in enumerate(str):
right[ord(c)] =  i
return right
def strStr(self, haystack, needle):
right = self.getRight(needle)
nn = len(needle)
nh = len(haystack)
i = 0
while i <= nh-nn:
j = nn - 1
while j >= 0:
if haystack[i+j] != needle[j]:
if i+nn < nh:
skip = nn - right[ord(haystack[i+nn])]
else:
return -1
break
j -= 1
if j == -1:
return i
i += skip
return -1``````

• I don't think Sunday is a stable algorithm on long suffix

e.g.

haystack: aaaaa

needle : baa

it looks like sunday will go to next text window

``````aaaaaaaa
^
baa
``````

but sadly it will only go one shift in haystack
cause the rightest most a is 2

``````aaaaaaaa
^
baa``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.