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
#include<stdio.h>
#include<string.h>
char s[10010],t[1000010];
int next[10010];
void getnext()
{
    int j=0,k=-1;
    next[0]=-1;
    while(s[j])
    {
        if(k==-1||s[j]==s[k])
        {
            k++;j++;
            if(s[k]!=s[j])next[j]=k;
            else next[j]=next[k];
        }
        else 
            k=next[k];
    }
}
int KMP()
{
    getnext();
    int i=0,j=0,ans=0;
    int l=strlen(s);
    while(t[i])
    {
        if(j==-1||t[i]==s[j])
        {
            i++;j++;
        }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX