kmp algorithm

1#include<bits/stdc++.h>
2using namespace std;
3void createlps(int lps[],string pattern,int n)
4{
5    int i=0;
6    int j=1;
7    lps[0]=0;
8    while(j<n)
9    {
10        if(pattern[i]==pattern[j])
11        {
12            lps[j]=i+1;
13            i++;
14            j++;
15        }
16        else
17        {
18            if(i!=0)
19            {
20                i=lps[i-1];
21            }
22            else
23            {
24                lps[j]=0;
25                j++;
26            }
27        }
28    }
29}
30void kmp(string str,string pattern,int n,int lps[])
31{
32    int i=0;
33    int j=0;
34    int size_of_str=str.size();
35    while(i<size_of_str)
36    {
37        if(pattern[j]==str[i])
38        {
39            i++;
40            j++;
41        }
42        if(j==n)
43        {
44            cout<<"Found at:"<<i-j;
45            j=lps[j-1];
46        }
47        else if(i<size_of_str&&pattern[j]!=str[i])
48        {
49            if(j!=0)
50            {
51                j=lps[j-1];
52            }
53            else
54            {
55                i++;
56            }
57        }
58    }
59}
60int main()
61{
62    string str;
63    cin>>str;
64    string pattern;
65    cin>>pattern;
66    int n=pattern.size();
67    int lps[n];
68    createlps(lps,pattern,n);
69    for(int i=0;i<n;i++)
70    {
71        cout<<lps[i]<<" ";
72    }
73    kmp(str,pattern,n,lps);
74    return 0;
75}
76

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}