Template

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
struct exkmp{

    int nxt[N],extend[N];

    void GetNext(){
        int a=0;
        nxt[0]=m;
        while(a<m-1 && t[a]==t[a+1]) a++;
        nxt[1]=a,a=1;
        for(int k=2;k<m;k++){
            int p=a+nxt[a]-1,L=nxt[k-a];
            if(k+L-1>=p){
                int j=(p-k+1)>0?p-k+1:0;
                while(k+j<m && t[k+j]==t[j]) j++;
                nxt[k]=j;
                a=k;
            }
            else nxt[k]=L;
        }
    }

    void GetExtend(){
        int a=0;
        while(a<m && s[a]==t[a]) a++;
        extend[0]=a,a=0;
        for(int k=1;k<n;k++){
            int p=a+extend[a]-1,L=nxt[k-a];
            if(k+L-1>=p){
                int j=(p-k+1)>0?(p-k+1):0;
                while(k+j<n && j<m && s[k+j]==t[j]) j++;
                extend[k]=j;
                a=k;
            }
            else extend[k]=L;
        }
    }

}K;