KMP算法

很简单的字符串匹配，KMP以及它的一个简单优化。整理成板子。

 1 #include<bits/stdc++.h> 
 2 #define f(i,a,b) for(int i=a;i<=b;i++)
 3 using namespace std;
 4 char s1[100005];
 5 char s2[100005];
 6 int nxt[100005];
 7 //void getnxt(char s[],int nxt[]){
 8 //    int len=strlen(s);
 9 //    nxt[0]=-1;
10 //    int i=0,j=-1;
11 //    while(i<len-1){
12 //        if(j==-1||s[i]==s[j]){
13 //            i++,j++;
14 //            nxt[i]=j;
15 //        }
16 //        else j=nxt[j]; 
17 //    }
18 //}
19 void getnxt(char s[],int nxt[]){
20     int len=strlen(s);
21     nxt[0]=-1;
22     int i=0,j=-1;
23     while(i<len-1){
24         if(j==-1||s[i]==s[j]){
25             i++,j++;
26             if(s[i]==s[j]) nxt[i]=nxt[j];
27             else nxt[i]=j;
28         }
29         else j=nxt[j]; 
30     }
31 }
32 int main(){
33     while(~scanf("%s",s1)){
34         if(s1[0]=='#') return 0;
35         scanf("%s",s2);
36         getnxt(s2,nxt);
37         int len1=strlen(s1);
38         int len2=strlen(s2);
39         int k=0;
40         int cnt=0;
41         int i=0;
42         while(i<=len1){
43             while(k<len2&&i<=len1){
44                 if(k==-1||s1[i]==s2[k]){
45                     i++,k++;
46                 }
47                 else{
48                     k=nxt[k];
49                 }
50             }
51             if(k==len2){
52                 cnt++;
53                 k=0;
54             }
55         }
56         printf("%d
",cnt);
57     }
58 }

上面是求有多少个独立子串，下面还有一个输出前缀数组和可不独立子串首次位置的代码。

 1 #include<bits/stdc++.h> 
 2 #define pf printf
 3 #define f(i,a,b) for(int i=a;i<=b;i++)
 4 using namespace std;
 5 char s1[100005];
 6 char s2[100005];
 7 int nxt[100005];
 8 void getnxt(char s[],int nxt[]){
 9     int len=strlen(s);
10     nxt[0]=-1;
11     int i=0,j=-1;
12     while(i<=len-1){
13         if(j==-1||s[i]==s[j]){
14             i++,j++;
15             nxt[i]=j;
16         }
17         else j=nxt[j]; 
18     }
19 }
20 //void getnxt(char s[],int nxt[]){
21 //    int len=strlen(s);
22 //    nxt[0]=-1;
23 //    int i=0,j=-1;
24 //    while(i<len-1){
25 //        if(j==-1||s[i]==s[j]){
26 //            i++,j++;
27 //            if(s[i]==s[j]) nxt[i]=nxt[j];
28 //            else nxt[i]=j;
29 //        }
30 //        else j=nxt[j]; 
31 //    }
32 //}
33 int main(){
34     while(~scanf("%s",s1)){
35         scanf("%s",s2);
36         getnxt(s2,nxt);
37         int len1=strlen(s1);
38         int len2=strlen(s2);
39         int k=0;
40         int cnt=0;
41         int i=0;
42         while(i<=len1){
43             while(k<len2&&i<=len1){
44                 if(k==-1||s1[i]==s2[k]){
45                     i++,k++;
46                 }
47                 else{
48                     k=nxt[k];
49                 }
50             }
51             if(k==len2){
52                 cnt++;
53                 k=nxt[len2-1];
54                 pf("%d
",i-len2+1);
55                 i--;
56             }
57         }
58         printf("%d",nxt[1]);
59         f(i,2,len2) printf(" %d",nxt[i]);
60     }
61 }