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 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 = *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 # lps 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