KMP
分类:
IT文章
•
2023-11-29 20:33:43
贴上几个不错的资料吧:
1、http://blog.csdn.net/v_july_v/article/details/7041827
2、http://www.cnblogs.com/yjiyjige/p/3263858.html
3、http://blog.csdn.net/lishaozhe1024/article/details/38454233
POJ 3461 Oulipo
http://poj.org/problem?id=3461
求出现次数 套KMP模版就ok
1 #include <cstdio>
2 #include <cstring>
3 #define N 1000010
4 #define M 100010
5 int nextt[M],len1,len2;
6 char str1[N],str2[M];
7 void get_nextt(){
8 int i=0,j=-1;
9 nextt[0]=-1;
10 while(i<len2){
11 if(j==-1||str2[i]==str2[j]){
12 ++i;++j;
13 nextt[i]=j;
14 }
15 else
16 j=nextt[j];
17 }
18 }
19 int kmp(){
20 int count=0,i=0,j=0;
21 while(i<len1){
22 if(str1[i]==str2[j]||j==-1){
23 ++i;++j;
24 }
25 else
26 j=nextt[j];
27 if(j==len2){
28 count++;
29 j=nextt[j];
30 }
31 }
32 return count;
33 }
34 int main(){
35 int numcase;
36 scanf("%d",&numcase);
37 while(numcase--){
38 scanf("%s%s",str2,str1);
39 len1=strlen(str1);
40 len2=strlen(str2);
41 get_nextt();
42 int x=kmp();
43 printf("%d
",x);
44 }
45 return 0;
46 }
View Code
HDOJ 1711 Number Sequence
http://acm.hdu.edu.cn/showproblem.php?pid=1711
求第一次出现的位置 KMP模版
1 #include<cstdio>
2 int a[1000010],b[10010],next[10010];
3 int T,n,m;
4 void getNext()
5 {
6 next[0]=-1;
7 int j=0,k=-1;
8 while(j<m-1)
9 {
10 if(k==-1||b[j]==b[k])
11 {
12 next[++j]=++k;
13 }else
14 {
15 k=next[k];
16 }
17 }
18 }
19 int KMP()
20 {
21 int i=0,j=0;
22 while(i<n&&j<m)
23 {
24 if(j==-1||a[i]==b[j])
25 {
26 i++;
27 j++;
28 }else
29 {
30 j=next[j];
31 }
32 }
33 if(j==m) return i-j+1;//题目里是从1开始编号的
34 else return -1;
35 }
36 int main()
37 {
38 scanf("%d",&T);
39 while(T--)
40 {
41 scanf("%d%d",&n,&m);
42 for(int i=0;i<n;i++) scanf("%d",&a[i]);
43 for(int i=0;i<m;i++) scanf("%d",&b[i]);
44 getNext();
45 printf("%d
", KMP());
46 }
47 return 0;
48 }
View Code
HDOJ 3746 Cyclic Necklace
http://acm.hdu.edu.cn/showproblem.php?pid=3746
在未优化过的next函数中,如果n%(n-next[n])==0就是最大循环节的个数,其中n-next[n]就是最大循环节的长度
1 #include<stdio.h>
2 #include<iostream>
3 #include<string.h>
4 #include<algorithm>
5 using namespace std;
6 const int MAXN=100010;
7 char str[MAXN];
8 int next[MAXN];
9
10 void getNext(char *p)
11 {
12 int j,k;
13 j=0;
14 k=-1;
15 int len=strlen(p);
16 next[0]=-1;
17 while(j<len)
18 {
19 if(k==-1||p[j]==p[k])
20 {
21 j++;
22 k++;
23 next[j]=k;
24 }
25 else k=next[k];
26 }
27 }
28 int main()
29 {
30 int T;
31 scanf("%d",&T);
32 while(T--)
33 {
34 scanf("%s",&str);
35 getNext(str);
36 int len=strlen(str);
37 if(next[len]==0)
38 {
39 printf("%d
",len);
40 continue;
41 }
42 int t=len-next[len];
43 if(len%t==0)printf("0
");
44 else
45 {
46 printf("%d
",t-len%t);
47 }
48 }
49 return 0;
50 }
View Code
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 char st1[20001],st2[12000001];
6 int next[1000001];
7 bool equ(int i,char a[],int j,char b[])
8 {
9 if(a[i]==b[j]&&a[i+1]==b[j+1]) return true;
10 return false;
11 }
12 void getnext()
13 {
14 int i,j,len=strlen(st1);
15 next[0]=-2;i=0;j=-2;
16 while(i<len)
17 {
18 if(j==-2||equ(i,st1,j,st1))
19 {
20 i+=2;j+=2;//++i;++j;
21 if(!equ(i,st1,j,st1)) next[i>>1]=j;
22 else next[i>>1]=next[j>>1];
23 }
24 else j=next[j>>1];
25 }
26 }
27 void kmp()
28 {
29 int i=0,j=0;
30 getnext();
31 int l1=strlen(st1),l2=strlen(st2);
32 int ans=0;
33 while(i<l2)
34 {
35 if(j==-2||equ(j,st1,i,st2))
36 i+=2,j+=2;
37 else j=next[ j>>1 ];
38 if(j==l1) ++ans,j=next[j>>1];
39 }
40 cout<<ans<<endl;
41 }
42 int main()
43 {
44 while(scanf("%s",st1)!=EOF){
45 scanf("%s",st2);
46 kmp();
47 }
48 return 0;
49 }