kmp c 2b 2b

1void computeLPSArray(char* pat, int M, int* lps)
2{
3    int len = 0;
4    lps[0] = 0;
5    int i = 1;
6    while (i < M) {
7        if (pat[i] == pat[len]) {
8            len++;
9            lps[i] = len;
10            i++;
11        }
12        else
13        {
14            if (len != 0) {
15                len = lps[len - 1];
16            }
17            else
18            {
19                lps[i] = 0;
20                i++;
21            }
22        }
23    }
24}
25int matchFound=0;
26void KMPSearch(char* pat, char* txt)
27{
28    matchFound=0;
29    int M = strlen(pat);
30    int N = strlen(txt);
31    int lps[M];
32    computeLPSArray(pat, M, lps);
33    int i = 0;
34    int j = 0;
35    while (i < N) {
36        if (pat[j] == txt[i]) {
37            j++;
38            i++;
39        }
40        if (j == M) {
41            matchFound++;
42//            printf("Found pattern at index %d ", i - j);
43            j = lps[j - 1];
44        }
45        else if (i < N && pat[j] != txt[i]) {
46            if (j != 0)
47                j = lps[j - 1];
48            else
49                i = i + 1;
50        }
51    }
52}