KMP Algorithm for Pattern Searching.

Pattern Search use case.


Pattern searching is quite important task in computer science. The Knuth–Morris–Pratt string-searching algorithm or simly KMP algorithm searches for occurrences of a certain pattern within a main text. An algorithm checks the characters from left to right. The pattern itself contains sufficient information to determine where the next match could begin bypassing re-examination of previously matched characters. The algorithm compares successive characters of pattern to parallel characters of text, moving from one to the next symbol when they match untill all word is recognized.

KMP Algorithm for Pattern Searching.



KMP has the nice advantage that it is guaranteed worst-case efficient. The well known real life application of Knuth–Morris–Pratt algorithm is string search in browsers, word processors and databases.


KMP Algorithm for Pattern Searching Python code:




def KMPSearch(pattern, text):
    M = len(pattern)
    N = len(text)
 
    # create lps[] that will hold the longest prefix suffix values for pattern
    lps = [0]*M
    j = 0 # index for pattern[]
 
    # Preprocess the pattern (calculate lps[] array)
    computeLPSArray(pattern, M, lps)
 
    i = 0 # index for text[]
    while i < N:
        if pattern[j] == text[i]:
            i += 1
            j += 1
 
        if j == M:
            print ("Found pattern at index", str(i-j))
            j = lps[j-1]
 
        # mismatch after j matches
        elif i < N and pattern[j] != text[i]:
             if j != 0:
                j = lps[j-1]
               
             else:
                i += 1
 
def computeLPSArray(pattern, M, lps):
    len = 0 # length of the previous longest prefix suffix
 
    lps[0] # lps[0] is always 0
    i = 1
 
    # the loop calculates lps[i] for i = 1 to M-1
    while i < M:
        if pat[i]== pattern[len]:
            len += 1
            lps[i] = len
            i += 1
        else:
            if len != 0:
                len = lps[len-1]
            else:
                lps[i] = 0
                i += 1
 
text = "QWERTYABBATRATRTABBA"
pattern = "ABBA"

KMPSearch(pattern, text)

OUT: Found pattern at index 6
Found pattern at index 16





See also related topics: