Algos/kmp.cpp at master · owishiboo/Algos · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
void createlps(char* pattern, int m, int* lps)
{
    int i=1;
    int j=0;
    lps[0] = 0;
    while(i<m){
        if(pattern[i]==pattern[j]){
            j++;
            lps[i] = j;
            i++;
        }
        else{
            if(j==0){
                lps[i]=0;
                i++;
            }
            else
                j = lps[j-1];
        }
    }
    //for(i=0;i<m;i++)cout<<lps[i]<<endl;
}
void searchpattern(char* text,char* pattern)
{
    int n = strlen(text);
    int m = strlen(pattern);
    int lps[m];
    createlps(pattern,m,lps);
    int i=0,j=0;
    while(i<n){
        if(text[i]==pattern[j]){
            i++;
            j++;
        }
        else{
            if(j==0)i++;
            else j=lps[j-1];
        }
        if(j==m){
            cout<<"Shift "<<i-j<<endl;
            j=lps[j-1];
        }


    }
}
int main()
{
    char text[] = "acacabacacabacacac";
    char pattern[] = "acac";
    searchpattern(text,pattern);
}