讲解

joylnwang的专栏

代码

这个是范神的模板，我研究了一下用法，po出来，以后忘了可以看看，先输入大串，再输入字串。

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
55
56
57
58
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <cstring>
using namespace std;
#define ll long long
const int LEN=1000005;
int next[LEN];
char s[LEN];
char sub[LEN];
void getnext(char sub[],int next[],int len2)
{
    int i=0,j=-1;
    next[0]=-1;
    while(i<len2)
    {
        if (j==-1||sub[i]==sub[j])
            i++,j++,next[i]=j;
        else j=next[j];
    }
}
int kmp(char s[],char sub[],int len1,int len2,int next[])
{
    int i=0,j=0;
    while(i<len1&&j<len2)
    {
        if (j==-1||s[i]==sub[j])
            i++,j++;
        else j=next[j];
    }
    if (j>=len2) return i-len2;
    else return -1;
}
int main(){
   while(cin>>s>>sub){
        getnext(sub,next,strlen(sub));
        int str=kmp(s,sub,strlen(s),strlen(sub),next);int pre=0;
        while(pre+str+strlen(sub)<=strlen(s)){
            cout<<"match position : "<<pre+str<<endl;
            for(int i=str+pre;i<str+pre+strlen(sub);i++)
                printf("%c",s[i]);
            puts("");
            //已经匹配到父串的末尾了
            if(pre+str+strlen(sub)==strlen(s))break;
            //更新已匹配过的长度
            pre=pre+str+1;
            cout<<"pre = "<<pre<<endl;
            //查找下一个匹配点
            str=kmp(s+pre,sub,strlen(s)-pre,strlen(sub),next);
            if(str==-1)break;
            
            system("pause");
        }
        cout<<"new example"<<endl;
   }
}