![\"C](\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Searching-for-Patterns-Set-2-KMP-Algorithm.png\")
\r\n<\/pre>\nPattern searching is an important problem in computer science. When we do search for a string in notepad\/word file or browser or database, pattern searching algorithms are used to show the search results.<\/p>\n
We have discussed Naive pattern searching algorithm in the previous post. The worst case complexity of Naive algorithm is O(m(n-m+1)). Time complexity of KMP algorithm is O(n) in worst case.<\/p>\n[ad type=”banner”]\n
KMP (Knuth Morris Pratt) Pattern Searching
\nThe Naive pattern searching algorithm doesn\u2019t work well in cases where we see many matching characters followed by a mismatching character. Following are some examples.<\/p>\n
txt[] = “AAAAAAAAAAAAAAAAAB”
\npat[] = “AAAAB”<\/p>\n
txt[] = “ABABABCABABABCABABABC”
\npat[] = “ABABAC” (not a worst case, but a bad case for Naive)
\nThe KMP matching algorithm uses degenerating property (pattern having same sub-patterns appearing more than once in the pattern) of the pattern and improves the worst case complexity to O(n). The basic idea behind KMP\u2019s algorithm is: whenever we detect a mismatch (after some matches), we already know some of the characters in the text of next window. We take advantage of this information to avoid matching the characters that we know will anyway match. Let us consider below example to understand this.<\/p>\n
Matching Overview
\ntxt = “AAAAABAAABA”
\npat = “AAAA”<\/p>\n
We compare first window of txt with pat
\ntxt = “AAAAABAAABA”
\npat = “AAAA” [Initial position]\nWe find a match. This is same as Naive String Matching.<\/p>\n
In the next step, we compare next window of txt with pat.
\ntxt = “AAAAABAAABA”
\npat = “AAAA” [Pattern shifted one position]\nThis is where KMP does optimization over Naive. In this
\nsecond window, we only compare fourth A of pattern
\nwith fourth character of current window of text to decide
\nwhether current window matches or not. Since we know
\nfirst three characters will anyway match, we skipped
\nmatching first three characters.<\/p>\n[ad type=”banner”]\n
Need of Preprocessing?
\nAn important question arises from above explanation,
\nhow to know how many characters to be skipped. To know
\nthis, we pre-process pattern and prepare an integer array
\nlps[] that tells us count of characters to be skipped.
\nPreprocessing Overview:<\/p>\n
KMP algorithm does preproceses pat[] and constructs an auxiliary lps[] of size m (same as size of pattern) which is used to skip characters while matching.
\nname lps indicates longest proper prefix which is also suffix.. A proper prefix is prefix with whole string not allowed. For example, prefixes of \u201cABC\u201d are \u201c\u201d, \u201cA\u201d, \u201cAB\u201d and \u201cABC\u201d. Proper prefixes are \u201c\u201d, \u201cA\u201d and \u201cAB\u201d. Suffixes of the string are \u201c\u201d, \u201cC\u201d, \u201cBC\u201d and \u201cABC\u201d.
\nFor each sub-pattern pat[0..i] where i = 0 to m-1, lps[i] stores length of the maximum matching proper prefix which is also a suffix of the sub-pattern pat[0..i].
\nlps[i] = the longest proper prefix of pat[0..i]\nwhich is also a suffix of pat[0..i].
\nNote : lps[i] could also be defined as longest prefix which is also proper suffix. We need to use proper at one place to make sure that the whole substring is not considered.<\/p>\n
Examples of lps[] construction:
\nFor the pattern \u201cAAAA\u201d,
\nlps[] is [0, 1, 2, 3]\n
For the pattern \u201cABCDE\u201d,
\nlps[] is [0, 0, 0, 0, 0]\n
For the pattern \u201cAABAACAABAA\u201d,
\nlps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]\n
For the pattern \u201cAAACAAAAAC\u201d,
\nlps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]\n
For the pattern \u201cAAABAAA\u201d,
\nlps[] is [0, 1, 2, 0, 1, 2, 3]\nSearching Algorithm:
\nUnlike Naive algorithm, where we slide the pattern by one and compare all characters at each shift, we use a value from lps[] to decide the next characters to be matched. The idea is to not match character that we know will anyway match.<\/p>\n
How to use lps[] to decide next positions (or to know number of characters to be skipped)?<\/p>\n
We start comparison of pat[j] with j = 0 with characters of current window of text.
\nWe keep matching characters txt[i] and pat[j] and keep incrementing i and j while pat[j] and txt[i] keep matching.
\nWhen we see a mismatch
\nWe know that characters pat[0..j-1] match with txt[i-j+1\u2026i-1] (Note that j starts with 0 and increment it only when there is a match).
\nWe also know (from above definition) that lps[j-1] is count of characters of pat[0\u2026j-1] that are both proper prefix and suffix.
\nFrom above two points, we can conclude that we do not need to match these lps[j-1] characters with txt[i-j\u2026i-1] because we know that these characters will anyway match. Let us consider above example to understand this.
\ntxt[] = “AAAAABAAABA”
\npat[] = “AAAA”
\nlps[] = {0, 1, 2, 3}<\/p>\n
i = 0, j = 0
\ntxt[] = “AAAAABAAABA”
\npat[] = “AAAA”
\ntxt[i] and pat[j[ match, do i++, j++<\/p>\n
i = 1, j = 1
\ntxt[] = “AAAAABAAABA”
\npat[] = “AAAA”
\ntxt[i] and pat[j[ match, do i++, j++<\/p>\n
i = 2, j = 2
\ntxt[] = “AAAAABAAABA”
\npat[] = “AAAA”
\npat[i] and pat[j[ match, do i++, j++<\/p>\n
i = 3, j = 3
\ntxt[] = “AAAAABAAABA”
\npat[] = “AAAA”
\ntxt[i] and pat[j[ match, do i++, j++<\/p>\n
i = 4, j = 4
\nSince j == M, print pattern found and resset j,
\nj = lps[j-1] = lps[3] = 3<\/p>\n
Here unlike Naive algorithm, we do not match first three
\ncharacters of this window. Value of lps[j-1] (in above
\nstep) gave us index of next character to match.
\ni = 4, j = 3
\ntxt[] = “AAAAABAAABA”
\npat[] = “AAAA”
\ntxt[i] and pat[j[ match, do i++, j++<\/p>\n
i = 5, j = 4
\nSince j == M, print pattern found and reset j,
\nj = lps[j-1] = lps[3] = 3<\/p>\n
Again unlike Naive algorithm, we do not match first three
\ncharacters of this window. Value of lps[j-1] (in above
\nstep) gave us index of next character to match.
\ni = 5, j = 3
\ntxt[] = “AAAAABAAABA”
\npat[] = “AAAA”
\ntxt[i] and pat[j] do NOT match and j > 0, change only j
\nj = lps[j-1] = lps[2] = 2<\/p>\n
i = 5, j = 2
\ntxt[] = “AAAAABAAABA”
\npat[] = “AAAA”
\ntxt[i] and pat[j] do NOT match and j > 0, change only j
\nj = lps[j-1] = lps[1] = 1<\/p>\n
i = 5, j = 1
\ntxt[] = “AAAAABAAABA”
\npat[] = “AAAA”
\ntxt[i] and pat[j] do NOT match and j > 0, change only j
\nj = lps[j-1] = lps[0] = 0<\/p>\n
i = 5, j = 0
\ntxt[] = “AAAAABAAABA”
\npat[] = “AAAA”
\ntxt[i] and pat[j] do NOT match and j is 0, we do i++.<\/p>\n
i = 6, j = 0
\ntxt[] = “AAAAABAAABA”
\npat[] = “AAAA”
\ntxt[i] and pat[j] match, do i++ and j++<\/p>\n
i = 7, j = 1
\ntxt[] = “AAAAABAAABA”
\npat[] = “AAAA”
\ntxt[i] and pat[j] match, do i++ and j++<\/p>\n
<\/p>\n