The Sunday Algorithm, better than BM and KMP.


  • 3
    I

    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

  • 0
    M

    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

Log in to reply
 

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