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.
Python Knowledge Base: Make coding great again.
- Updated:
2024-12-29 by Andrey BRATUS, Senior Data Analyst.
KMP Algorithm for Pattern Searching Python code:
KMP Algorithm code result:
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.
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