首页 > 代码库 > HDU 5782 Cycle（KMP+Hash）
HDU 5782 Cycle（KMP+Hash）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5782
【题目大意】
给出两个字符串，判断他们每一个前缀是否循环同构，循环同构的意思就是，字符串首位相接拼成一个环，两个环通过旋转可以相等。
【题解】
这道题用到了一个神奇的结论，如果S字符串和T字符串循环同构，那么必有S=u+v，T=v+u，而且u和v必有一个是最长匹配。
那么根据这个结论，我们可以用KMP算法在T中找S的最长前缀，也就是每次匹配到i时候的j。那么对于T的前缀和S的后缀，我们直接用哈希来判断是否相等，这样子就可以计算出两个串的前缀是否循环同构了。
【代码】
#include <cstdio>#include <cstring>using namespace std;const int N=10005,base=233;typedef long long ll; int T,nxt[N],ans[N];char a[N],b[N];ll hash[2][N],p[N];ll get_hash(int t,int L,int R){ return hash[t][R]-hash[t][L-1]*p[R-L+1];}int check(int t,int m,int n){ if(m==n)return 1; return get_hash(t,m+1,n)==get_hash(t^1,1,n-m);}void kmp(int n,char*a,int m,char*b,int t){ int i,j; for(nxt[1]=j=0,i=2;i<=n;nxt[i++]=j){ while(j&&a[j+1]!=a[i])j=nxt[j]; if(a[j+1]==a[i])j++; } for(j=0,i=1;i<=m;i++){ while(j&&a[j+1]!=b[i])j=nxt[j]; if(a[j+1]==b[i]){ j++; if(!ans[i])ans[i]=check(t,j,i); }if(j==n)j=nxt[j]; }}int main(){ for(int i=p[0]=1;i<N;i++)p[i]=p[i-1]*base; while(~scanf(" %s %s",a+1,b+1)){ int n=strlen(a+1); for(int i=1;i<=n;i++){ ans[i]=0; hash[0][i]=hash[0][i-1]*base+a[i]; hash[1][i]=hash[1][i-1]*base+b[i]; }kmp(n,a,n,b,0); kmp(n,b,n,a,1); for(int i=1;i<=n;i++)printf("%d",ans[i]); puts(""); }return 0;}
HDU 5782 Cycle（KMP+Hash）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。