rarezhang / kmp Goto Github PK

searches for occurrences of a "pattern" P within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.
read more

The length of the longest proper prefix in the (sub)pattern that matches a proper suffix in the same (sub)pattern.

example:
"abababca":

• third cell: first three characters ("aba")

  • prefixes ("a" and "ab")
  • suffixes ("a" and "ba")
  • the proper prefix "a" matches the proper suffix "a" --> value=1

• cell 4: ("abab")

  • prefixes ("a","ab","aba")
  • suffixes ("b","ab","bab")
  • matches = "ab" --> value=2

• cell 5: ("ababa")

  • prefixes ("a","ab","aba","abab")
  • suffixes ("a","ba","aba","baba")
  • matches = "aba" --> value=3

• cell 7: ("abababc")

  • there aren’t going to be any matches; all the suffixes will end with the letter “c”, and none of the prefixes will

def kmp_table(s):   
    """
    Partial match table
    O(K): K=length(s) 
    """
    length = len(s)
    partial_match_table = [0]*length
    s = list(s)
    i,j=0,1
    while i<length and j<length:
        if s[i]==s[j]:  # case 1: the substring continues  
            partial_match_table[j]=i+1
            i+=1
            j+=1
        else:  # case 2: the substring doesn't continues, but can fall back
            if i==0:
                partial_match_table[j]=0
                j+=1
            else:  # case 3: run out of candates
                i = partial_match_table[i-1]
    return partial_match_table

s="ababab"
print(kmp_table(s))
# [0, 0, 1, 2, 3, 4]

code visualization

We can use the values in the partial match table to skip ahead (rather than redoing unnecessary old comparisons) when we find partial matches.
If a partial match of length partial_match_length is found and table[partial_match_length] > 1, we may skip ahead partial_match_length - table[partial_match_length - 1] characters.

example:
matching the pattern "abababca" against the text "bacbababaabcbab"

• partial_match_length=1
• table[partial_match_length - 1]=table[0]=0
• don't skip

• partial_match_length=5
• table[partial_match_length - 1]=table[4]=3
• skip=partial_match_length-table[4]=5-3=1

• partial_match_length=3
• table[partial_match_length - 1]=table[2]=1
• skip=partial_match_length-table[2]=3-1=2

• pattern is longer than the remaining characters in the text, so we know there’s no match.

def kmp_search(P, S, kmp_table):
    """
    O(n)
    P: the pattern(word) sought
    S: the text to be searched
    return: an integer (the zero-based position in S at which P is found)

    """
    m = 0  # the beginning of the current match in S
    i = 0  # the position of the current character in P
    
    while m + i < len(S):
        if P[i] == S[m+i]:
            if i == len(P) - 1:
                return m
            i += 1
        else:
            if kmp_table[i] > 0:
                m = m + i - kmp_table[i]
                i = kmp_table[i]
            else:
                m += 1
                i = 0
    return None  # have searched all of S unsuccessfully
    
s="ababab"
print(kmp_search('aba', s, kmp_table(s)))
# 0 

code visualization