KMP

最近重新学习了一下KMP算法，然后重新做了自己的模板。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1686

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAXN 10010
 7 #define MAXM 1000010
 8 char str1[MAXN];
 9 char str2[MAXM];
10 int Next[MAXN];
11 
12 int len1,len2;
13 
14 void Get_Next(){
15     int j=0,k=-1;
16     Next[0]=-1;
17     while(j<len1){
18         if(k==-1||str1[j]==str1[k]){
19             j++,k++;
20             Next[j]=k;
21         }else 
22             k=Next[k];
23     }
24 }
25 
26 int KMP(){
27     int i=0,j=0,ans=0;
28     while(j<len1&&i<len2){
29         if(j==-1||str1[j]==str2[i]){
30             i++,j++;
31             //相等时说明找到了，此时要回溯
32             if(j==len1){
33             ans++;
34             j=Next[j];
35         }
36         }else 
37             j=Next[j];
38     }
39     return ans;
40 }
41 
42 
43 int main(){
44     int _case;
45     scanf("%d",&_case);
46     while(_case--){
47         scanf("%s%s",str1,str2);
48         len1=strlen(str1),len2=strlen(str2);//str1模式串，str2主串
49         Get_Next();
50         int ans=KMP();
51         printf("%d\n",ans);
52     }
53     return 0;
54 }

View Code

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1867

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define MAXN 100100
 6 int Next_a[MAXN];
 7 int Next_b[MAXN];
 8 char str1[MAXN];
 9 char str2[MAXN];
10 
11 void Get_Next(char str[],int Next[]){
12     Next[0]=-1;
13     int j=0,k=-1,len=strlen(str);
14     while(j<len){
15         if(k==-1||str[k]==str[j]){
16             j++,k++;
17             Next[j]=k;
18         }else 
19             k=Next[k];
20     }
21 }
22 
23 int KMP(char str1[],char str2[],int Next[]){
24     int i=0,j=0;
25     int len1=strlen(str1);
26     int len2=strlen(str2);
27     while(i<len1&&j<len2){
28         if(j==-1||str1[i]==str2[j]){
29             i++,j++;
30         }else 
31             j=Next[j];
32     }
33     //这边得注意一下
34     if(i==len1)return j;
35     return 0; 
36 }
37     
38 
39 int main(){
40     while(~scanf("%s%s",str1,str2)){
41         Get_Next(str1,Next_a);
42         Get_Next(str2,Next_b);
43         int len2=KMP(str1,str2,Next_b);
44         int len1=KMP(str2,str1,Next_a);
45         if(len1==len2){
46             if(strcmp(str1,str2)<0){
47                 printf("%s%s\n",str1,str2+len2);
48             }else 
49                 printf("%s%s\n",str2,str1+len1);
50         }else if(len1<len2){
51             printf("%s%s\n",str1,str2+len2);
52         }else {
53             printf("%s%s\n",str2,str1+len1);
54         }
55     }
56     return 0;
57 }

View Code

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3374

思路：输出次数就是字符串的循环结，然后求最大最小的位置就是字符串的最小表示法了。

cxlove大神讲的很清楚：http://blog.csdn.net/acm_cxlove/article/details/7909087

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define MAXN 1000100
 6 int Next[MAXN];
 7 char str[MAXN];
 8 
 9 void Get_Next(){
10     Next[0]=-1;
11     int len=strlen(str),j=0,k=-1;
12     while(j<len){
13         if(k==-1||str[j]==str[k]){
14             j++,k++;
15             Next[j]=k;
16         }else 
17             k=Next[k];
18     }
19 }
20 
21 //字符串最小表示法:
22 int GetMin(){
23     int len=strlen(str),p1=0,p2=1,k=0,tmp;
24     while(p1<len&&p2<len&&k<len){
25         tmp=str[(p1+k)%len]-str[(p2+k)%len];
26         if(tmp==0){ k++; }
27         else {
28             tmp<0?(p2=p2+k+1):(p1=p1+k+1);
29             if(p1==p2)p2++;
30             k=0;
31         }
32     }
33     return p1<p2?p1:p2;
34 }
35 
36 //最大表示法与最小表示法类似
37 int GetMax(){
38     int len=strlen(str),p1=0,p2=1,k=0,tmp;
39     while(p1<len&&p2<len&&k<len){
40         tmp=str[(p1+k)%len]-str[(p2+k)%len];
41         if(tmp==0){ k++; }
42         else {
43             tmp>0?(p2=p2+k+1):(p1=p1+k+1);
44             if(p1==p2)p2++;
45             k=0;
46         }
47     }
48     return p1<p2?p1:p2;
49 }
50 
51     
52 int main(){
53     while(~scanf("%s",str)){
54         int len=strlen(str);
55         Get_Next();
56         int t=len-Next[len];//t即为字符串的循环结（最小）
57         if(len%t==0)t=len/t; 
58         else t=1;
59         int pmin=GetMin()+1;
60         int pmax=GetMax()+1;
61         printf("%d %d %d %d\n",pmin,t,pmax,t);
62     }
63     return 0;
64 }

View Code

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2594

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define MAXN 50050
 6 int Next[MAXN];
 7 char str1[MAXN];
 8 char str2[MAXN];
 9 
10 void Get_Next(){
11     Next[0]=-1;
12     int len=strlen(str1);
13     int j=0,k=-1;
14     while(j<len){
15         if(k==-1||str1[j]==str1[k]){
16             j++,k++;
17             Next[j]=k;
18         }else 
19             k=Next[k];
20     }
21 }
22 
23 void KMP(){
24     int len1=strlen(str1);
25     int len2=strlen(str2);
26     int i=0,j=0;
27     if(len2-len1>0)i=len2-len1;//这点很重要，要防止出现这种rie mmriemm情况；
28     while(i<len2&&j<len1){
29         if(j==-1||str1[j]==str2[i]){
30             i++,j++;
31         }else 
32             j=Next[j];
33     }
34     if(j==0){
35         puts("0");
36     }else {
37         for(i=0;i<j;i++){
38             printf("%c",str1[i]);
39         }
40         printf(" %d\n",j);
41     }
42 }
43 
44 
45 int main(){
46     while(~scanf("%s",str1)){
47         scanf("%s",str2);
48         Get_Next();
49         KMP();
50     }
51     return 0;
52 }

View Code

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4300

题意：orz..题意都理解了半天！！！

说的是给你一个26个字母表，每个字母对应的位置的字母就是明文所对应的密文，然后再给你一个字符串，字符串前部分为密文，后部分为前部分密文所对应的明文。而且密文和明文不会嵌套在一起。但是明文只显示了一部分，现在需要你补充所缺少的明文。就是先取字符串的前一半，将其转成明文后与后一半去匹配，最后返回模式串中指针的位置pos,然后原字符串中len-pos的位置就是明文开始的位置了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define MAXN 100010
 6 int Next[MAXN];
 7 char s[33],ss[33];
 8 char str[MAXN];
 9 char str1[MAXN];
10 
11 void Get_Next(){
12     Next[0]=-1;
13     int len=strlen(str1),j=0,k=-1;
14     while(j<len){
15         if(k==-1||str1[j]==str1[k]){
16             j++,k++;
17             Next[j]=k;
18         }else 
19             k=Next[k];
20     }
21 }
22 
23 int KMP(char str1[],char str2[]){
24     int len1=strlen(str1);
25     int len2=strlen(str2);
26     int i=0,j=0;
27     while(i<len1&&j<len2){
28         if(j==-1||str1[i]==str2[j]){
29             i++,j++;
30         }else
31             j=Next[j];
32     }
33     return j;
34 }
35 
36 
37 int main(){
38     int _case;
39     scanf("%d",&_case);
40     while(_case--){
41         scanf("%s%s",s,str);
42         for(int i=0;i<26;i++){
43             ss[s[i]-'a']=i+'a';
44         }
45         int len=strlen(str);
46         for(int i=0;i<len/2;i++){
47             str1[i]=ss[str[i]-'a'];//转成明文再去匹配
48         }
49         str1[len/2]='\0';
50         Get_Next();
51         int pos=KMP(str+len/2,str1);
52         for(int i=0;i<len-pos;i++)printf("%c",str[i]);
53         for(int i=0;i<len-pos;i++)printf("%c",ss[str[i]-'a']);
54         puts("");
55     }
56     return 0;
57 }
58 
59 
60 
61

View Code

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3746

思路：这题的关键点就是要知道字符串循环节的求法（Next数组的运用），然后注意就是要取模了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define MAXN 100100
 6 int Next[MAXN];
 7 char str[MAXN];
 8 int len;
 9 
10 void Get_Next(){
11     Next[0]=-1;
12     int j=0,k=-1;
13     while(j<len){
14         if(k==-1||str[j]==str[k]){
15             j++,k++;
16             Next[j]=k;
17         }else
18             k=Next[k];
19     }
20 }
21 
22 
23 int main(){
24     int _case;
25     scanf("%d",&_case);
26     while(_case--){
27         scanf("%s",str);
28         len=strlen(str);
29         Get_Next();
30         int l=len-Next[len];//循环节长度
31         if(len!=l&&len%l==0){
32             puts("0");
33         }else {
34             l=l-Next[len]%l;//要mod上循环节的长度，纸上yy就知道了。
35             printf("%d\n",l);
36         }
37     }
38     return 0;
39 }

View Code