Prints occurrences of txt[] in pat[]
| 40 | } |
| 41 | // Prints occurrences of txt[] in pat[] |
| 42 | void KMPSearch(string pat, string txt) |
| 43 | { |
| 44 | int M = pat.length(); |
| 45 | int N = txt.length(); |
| 46 | |
| 47 | // create lps[] that will hold the longest prefix suffix |
| 48 | // values for pattern |
| 49 | int lps[M]; |
| 50 | |
| 51 | // Preprocess the pattern (calculate lps[] array) |
| 52 | computeLPSArray(pat, M, lps); |
| 53 | |
| 54 | int i = 0; // index for txt[] |
| 55 | int j = 0; // index for pat[] |
| 56 | while (i < N) |
| 57 | { |
| 58 | if (pat[j] == txt[i]) |
| 59 | { |
| 60 | j++; |
| 61 | i++; |
| 62 | } |
| 63 | |
| 64 | if (j == M) |
| 65 | { |
| 66 | printf("Found pattern at index %d ", i - j); |
| 67 | j = lps[j - 1]; |
| 68 | } |
| 69 | |
| 70 | // mismatch after j matches |
| 71 | else if (i < N && pat[j] != txt[i]) |
| 72 | { |
| 73 | // Do not match lps[0..lps[j-1]] characters, |
| 74 | // they will match anyway |
| 75 | if (j != 0) |
| 76 | j = lps[j - 1]; |
| 77 | else |
| 78 | i = i + 1; |
| 79 | } |
| 80 | } |
| 81 | } |
| 82 | |
| 83 | // Driver program to test above function |
| 84 | int main() |
no test coverage detected