<jupyter_start><jupyter_text>KMP Algorithm for Pattern SearchingGiven a text `txt[0..n-1]` and a pattern `pat[0..m-1]`, write a function search(char `pat[]`, char `txt[]`) that prints all occurrences of `pat[]` in `txt[]`. You may assume that `n > m`.**Examples:**```bashInput:  txt[] = "THIS IS A TEST TEXT"        pat[] = "TEST"Output: Pattern found at index 10Input:  txt[] =  "AABAACAADAABAABA"        pat[] =  "AABA"Output: Pattern found at index 0        Pattern found at index 9        Pattern found at index 12```Pattern 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.  Naive algorithm for Pattern Searching**What is the best case?**The best case occurs when the first character of the pattern is not present in text at all.```bashtxt[] = "AABCCAADDEE"; pat[] = "FAA";```The number of comparisons in best case is $O(n)$.**What is the worst case?**The worst case of Naive Pattern Searching occurs in following scenarios.1. When all characters of the text and pattern are same.    ```bash    txt[] = "AAAAAAAAAAAAAAAAAA";     pat[] = "AAAAA";    ```2. Worst case also occurs when only the last character is different.    ```bash    txt[] = "AAAAAAAAAAAAAAAAAB";     pat[] = "AAAAB";    ```    The number of comparisons in the worst case is $O(m*(n-m+1))$. Although strings which have repeated characters are not likely to appear in English text, they may well occur in other applications (for example, in binary texts). The KMP matching algorithm improves the worst case to $O(n)$.<jupyter_code># Python3 program for Naive Pattern 
# Searching algorithm 
def search(pat, txt): 
    M = len(pat) 
    N = len(txt) 
    # A loop to slide pat[] one by one */ 
    for i in range(N - M + 1): 
        j = 0
        # For current index i, check  
        # for pattern match */ 
        while(j < M): 
            if (txt[i + j] != pat[j]): 
                break
            j += 1
  
        if (j == M):  
            print("Pattern found at index ", i) 
            
# Driver Code 
if __name__ == '__main__': 
    txt = "AABAACAADAABAAABAA"
    pat = "AABA"
    search(pat, txt)<jupyter_output>Pattern found at index  0
Pattern found at index  9
Pattern found at index  13<jupyter_text>KMP (<NAME>) Pattern SearchingThe Naive pattern searching algorithm doesn’t work well in cases where we see many matching characters followed by a mismatching character. Following are some examples.```bash   txt[] = "AAAAAAAAAAAAAAAAAB"   pat[] = "AAAAB"   txt[] = "ABABABCABABABCABABABC"   pat[] =  "ABABAC" (not a worst case, but a bad case for Naive)```The 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’s algorithm is: whenever we detect a mismatch (after some matches), we already know some of the characters in the text of the 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.```bashMatching Overviewtxt = "AAAAABAAABA" pat = "AAAA"We compare first window of txt with pattxt = "AAAAABAAABA" pat = "AAAA"  [Initial position]We find a match. This is same as Naive String Matching.In the next step, we compare next window of txt with pat.txt = "AAAAABAAABA" pat =  "AAAA" [Pattern shifted one position]```This is where KMP does optimization over Naive. In this second window, we only compare `fourth A` of pattern with fourth character of current window of text to decide whether current window matches or not. Since we know first three characters will anyway match, we skipped matching first three characters. **Need of Preprocessing?**An important question arises from the above explanation, how to know how many characters to be skipped. To know this, we pre-process pattern and prepare an integer array `lps[]` that tells us the count of characters to be skipped.```lps[i] = the longest proper prefix of pat[0..i]               which is also a suffix of pat[0..i]. ```For example, prefixes of “ABC” are “”, “A”, “AB” and “ABC”. Proper prefixes are “”, “A” and “AB”. Suffixes of the string are “”, “C”, “BC” and “ABC”.```bashExamples of lps[] construction:For the pattern “AAAA”, lps[] is [0, 1, 2, 3]For the pattern “ABCDE”, lps[] is [0, 0, 0, 0, 0]For the pattern “AABAACAABAA”, lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]For the pattern “AAACAAAAAC”, lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4] For the pattern “AAABAAA”, lps[] is [0, 1, 2, 0, 1, 2, 3]```  Searching Algorithm:Unlike 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 a character that we know will anyway match.**How to use `lps[]` to decide next positions (or to know a number of characters to be skipped)?**1. We start comparison of pat[j] with j = 0 with characters of current window of text.2. We keep matching characters txt[i] and pat[j] and keep incrementing i and j while pat[j] and txt[i] keep matching.3. When we see a mismatch    - We know that characters pat[0..j-1] match with txt[i-j…i-1] (Note that j starts with 0 and increment it only when there is a match).    - We also know (from above definition) that lps[j-1] is count of characters of pat[0…j-1] that are both proper prefix and suffix.    - From above two points, we can conclude that we do not need to match these lps[j-1] characters with txt[i-j…i-1] because we know that these characters will anyway match. Let us consider above example to understand this.    ```bashtxt[] = "AAAAABAAABA" pat[] = "AAAA"lps[] = {0, 1, 2, 3} i = 0, j = 0txt[] = "AAAAABAAABA" pat[] = "AAAA"txt[i] and pat[j] match, do i++, j++i = 1, j = 1txt[] = "AAAAABAAABA" pat[] = "AAAA"txt[i] and pat[j] match, do i++, j++i = 2, j = 2txt[] = "AAAAABAAABA" pat[] = "AAAA"pat[i] and pat[j] match, do i++, j++i = 3, j = 3txt[] = "AAAAABAAABA" pat[] = "AAAA"txt[i] and pat[j] match, do i++, j++i = 4, j = 4Since j == M, print pattern found and reset j,j = lps[j-1] = lps[3] = 3Here unlike Naive algorithm, we do not match first three characters of this window. Value of `lps[j-1]` (in above step) gave us index of next character to match.i = 5, j = 3txt[] = "AAAAABAAABA" pat[] =   "AAAA"txt[i] and pat[j] do NOT match and j > 0, change only jj = lps[j-1] = lps[2] = 2i = 5, j = 2txt[] = "AAAAABAAABA" pat[] =    "AAAA"txt[i] and pat[j] do NOT match and j > 0, change only jj = lps[j-1] = lps[1] = 1 i = 5, j = 1txt[] = "AAAAABAAABA" pat[] =     "AAAA"txt[i] and pat[j] do NOT match and j > 0, change only jj = lps[j-1] = lps[0] = 0i = 5, j = 0txt[] = "AAAAABAAABA" pat[] =      "AAAA"txt[i] and pat[j] do NOT match and j is 0, we do i++.i = 6, j = 0txt[] = "AAAAABAAABA" pat[] =       "AAAA"txt[i] and pat[j] match, do i++ and j++i = 7, j = 1txt[] = "AAAAABAAABA" pat[] =       "AAAA"txt[i] and pat[j] match, do i++ and j++We continue this way...```<jupyter_code># Python program for KMP Algorithm 
def KMPSearch(pat, txt): 
    M = len(pat) 
    N = len(txt) 
  
    # create lps[] that will hold the longest prefix suffix  
    # values for pattern 
    lps = [0]*M 
    j = 0 # index for pat[] 
  
    # Preprocess the pattern (calculate lps[] array) 
    lps = computeLPSArray(pat, M, lps) 
    print(f'lps is {lps}')
    i = 0 # index for txt[] 
    while i < N: 
        if pat[j] == txt[i]: 
            i += 1
            j += 1
  
        if j == M: 
            print(f"Found pattern at index {i-j}")
            j = lps[j-1] 
  
        # mismatch after j matches 
        elif i < N and pat[j] != txt[i]: 
            # Do not match lps[0..lps[j-1]] characters, 
            # they will match anyway 
            if j != 0: 
                j = lps[j-1] 
            else: 
                i += 1
                
def computeLPSArray(pat, 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]== pat[len]: 
            len += 1
            lps[i] = len
            i += 1
        else: 
            # This is tricky. Consider the example. 
            # AAACAAAA and i = 7. The idea is similar  
            # to search step. 
            if len != 0: 
                len = lps[len-1] 
                # Also, note that we do not increment i here 
            else: 
                lps[i] = 0
                i += 1
    return lps
                
txt = "ABABDABACDABABCABAB"
pat = "ABABCABAB"
KMPSearch(pat, txt)<jupyter_output>lps is [0, 0, 1, 2, 0, 1, 2, 3, 4]
Found pattern at index 10
{'fraction_non_alphanumeric': 0.11597324566375694, 'fraction_numerical': 0.0172316063938329, 'mean_word_length': 2.872695346795435, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 3, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '122113', 'license': 'MIT', 'n_tokens_mistral': 2967, 'n_tokens_neox': 2720, 'n_words': 1254, 'path': '10.Algorithms_Data_Structure/Searching_n_Sorting/05 KMP Algorithm for Pattern Searching.ipynb', 'repo_name': 'cuicaihao/Data_Science_Python', 'size': '8833'}