看了这位大神的博客:http://www.cnblogs.com/wuyiqi/archive/2012/01/05/2313746.html
花了一个上午的时间把题都A了,对KMP的前缀与后缀,以及循环节问题有了一定的了解。特别是next[]数组,可以记录前缀和后缀相同的长度,如果这个长度没有超过一半的话,就可以求字符串的循环节n-next[n]。
先附下KMP模版:
void getnext() { int i=0,j=-1; next[i]=j; while(i<m) { while(j>=0&&b[i]!=b[j]) j=next[j]; i++;j++; next[i]=j; } } void KMP() { int i=0,j=0; while(i<n) { while(j>=0&&a[i]!=b[j]) j=next[j]; i++;j++; if(j==m) { report(i-j); j=next[j]; } } }
下面是一些hdu题的代码:
hdu3336:
题意:求给定字符串的所有子串中含前缀的数量
这里用了dp的思想,当前状态能够通过当前的最大前缀的前缀数量+1得来。
dp[i]表示以s[i]结尾并且必须包含第i个位置的子串中是前缀的数量。
以i结尾,首先包含从1到i这整个子串作为一个前缀,然后计算从1-i这个子串中是前缀的数量。j=next[i]到i之间已经不含以s[i]结尾的字符串了,又因为s[0]-s[j-1]==s[i-j]-s[i-1],,所以d[i]还要加上dp[j],即后缀中可能是前缀的子串数。
dp[i]=dp[next[i]]+1;
#include<iostream> #include<vector> #include<string> #include<queue> #include<cstdio> #include<cstring> #define maxn 200005 #define INF 0xfffffff #define MOD 10007 using namespace std; int n; char s[maxn]; int next[maxn];//next[i]=j表示与s[0-j]与s[i-j--i]相等 int dp[maxn];//dp[i]表示i之前的的前缀之和 void getnext() { int i=0,j=-1; next[i]=j; while(i<n) { while(j>=0&&s[i]!=s[j]) j=next[j]; i++;j++; next[i]=j; } } int main() { int t; cin>>t; while(t--) { cin>>n; cin>>s; getnext(); dp[0]=0; int sum=0; for(int i=1;i<=n;i++) { dp[i]=dp[next[i]]+1; sum=(sum+dp[i])%MOD; } cout<<sum<<endl; } return 0; }
hdu3746
题意:求最少需要在结尾后面补几个字符才能凑成两个循环.
这就是一个典型的求循环节的问题,只要求出循环节,再判断当前字符串的长度和循环节的大小关系就能得出答案。
#include<iostream> #include<vector> #include<string> #include<queue> #include<cstdio> #include<cstring> #define maxn 100005 #define INF 0xfffffff using namespace std; char s[maxn]; int n,next[maxn]; void getnext() { int i=0,j=-1; next[i]=j; while(i<n) { while(j>=0&&s[i]!=s[j]) j=next[j]; i++;j++; next[i]=j; } } int main() { int t; cin>>t; while(t--) { scanf("%s",s); n=strlen(s); getnext(); //cout<<0<<endl; int m=n-next[n];//循环节长度 if(n==m) { printf("%d\n",m); continue; } //cout<<n-2*next[n]<<endl; if(n%m==0) printf("0\n"); else printf("%d\n",m-n%m); } return 0; }
hdu2087
题意:从一个字符串中最多能出现多少个匹配串。
这里只要把每次打到匹配串的长度之后,j开始的位置指向0就行了。
#include<iostream> #include<vector> #include<string> #include<queue> #include<cstdio> #include<cstring> #define maxn 2005 #define INF 0xfffffff using namespace std; int ans; int next[maxn]; char a[maxn],b[maxn];//模式串为b int n,m; void getnext() { int i=0,j=-1; next[i]=j; while(i<m) { while(j>=0&&b[i]!=b[j]) j=next[j]; i++; j++; next[i]=j; } } void KMP() { int i=0,j=0; while(i<n) { while(j>=0&&a[i]!=b[j]) j=next[j]; //cout<<i<<' '<<j<<endl; i++;j++; if(j==m) { ans++; //cout<<i<<' '<<j<<endl; j=0; } } } int main() { while(cin>>a) { if(a[0]=='#') break; cin>>b; n=strlen(a),m=strlen(b); //cout<<n<<' '<<m<<endl; getnext(); /* for(int i=0;i<=m;i++) { cout<<i<<' '<<next[i]<<endl; } */ ans=0; KMP(); cout<<ans<<endl; } return 0; }
hdu2594
题目:求最长的a的前缀同时满足是b的后缀
这里直接把b串连在a串后面,然后用kmp跑一次,最后判断next[n+m]的大小。因为无论是前缀还是后缀,都是a,b的子串,所以应该比a,b的长度要小,所以用循环来不断套next[]。
#include<iostream> #include<vector> #include<string> #include<queue> #include<cstdio> #include<cstring> #define maxn 50005 #define INF 0xfffffff using namespace std; char a[maxn*2],b[maxn]; int next[maxn*2]; int n,m,ans; void getnext() { int i=0,j=-1; next[i]=j; while(i<n+m) { while(j>=0&&a[i]!=a[j]) j=next[j]; i++; j++; next[i]=j; } ans=next[n+m]; while(ans>n)//后缀串要比两个串都要短 { ans=next[ans]; } while(ans>m) { ans=next[ans]; } } int main() { while(scanf("%s",a)!=EOF) { scanf("%s",b); n=strlen(a),m=strlen(b); for(int i=n;i<n+m;i++) { a[i]=b[i-n]; } a[n+m+1]='\0'; getnext(); if(ans==0) cout<<ans<<endl; else { for(int i=0;i<ans;i++) { cout<<a[i]; } cout<<' '; cout<<ans<<endl; } } return 0; }