首页 > 代码库 > 【枚举】【字符串哈希】Gym - 101164K - Cutting
【枚举】【字符串哈希】Gym - 101164K - Cutting
给你A B两个串,让你切B串两刀,问你能否把切开的三个串拼成A。
哈希显然。
#include<cstdio> #include<cstring> using namespace std; typedef unsigned long long ull; const ull MOD1=2000000011; const ull MOD2=1000000007; const ull base1=10007; const ull base2=10009; int n; char a[10010],b[10010]/*,d[10010],e[10010]*/; ull b1s[10010],b2s[10010]; ull hs[3][10010]; const int c[7][4]={{0,0,0,0},{0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},{0,3,1,2},{0,3,2,1}}; int main(){ b1s[0]=b2s[0]=1; scanf("%s%s",b+1,a+1); // memcpy(d,b,sizeof(b)); // memcpy(e,a,sizeof(a)); n=strlen(a+1); for(int i=1;i<=n;++i){ b1s[i]=b1s[i-1]*base1%MOD1; b2s[i]=b2s[i-1]*base2%MOD2; } ull hs2[3]={0}; for(int i=1;i<=n;++i){ if(a[i]<=‘Z‘){ a[i]+=32; } if(b[i]<=‘Z‘){ b[i]+=32; } hs2[1]=(hs2[1]*base1%MOD1+b[i]-‘a‘)%MOD1; hs2[2]=(hs2[2]*base2%MOD2+b[i]-‘a‘)%MOD2; hs[1][i]=(hs[1][i-1]*base1%MOD1+a[i]-‘a‘)%MOD1; hs[2][i]=(hs[2][i-1]*base2%MOD2+a[i]-‘a‘)%MOD2; } ull hs1[3][4]; int len[4]; len[0]=0; for(int i=1;i<=n-2;++i){ for(int j=i+1;j<=n-1;++j){ len[1]=i; len[2]=j-i; len[3]=n-j; hs1[1][1]=hs[1][i]; hs1[1][2]=(hs[1][j]-hs[1][i]*b1s[len[2]]%MOD1+MOD1)%MOD1; hs1[1][3]=(hs[1][n]-hs[1][j]*b1s[len[3]]%MOD1+MOD1)%MOD1; hs1[2][1]=hs[2][i]; hs1[2][2]=(hs[2][j]-hs[2][i]*b2s[len[2]]%MOD2+MOD2)%MOD2; hs1[2][3]=(hs[2][n]-hs[2][j]*b2s[len[3]]%MOD2+MOD2)%MOD2; for(int k=1;k<=6;++k){ if(((hs1[1][c[k][1]]*b1s[len[c[k][2]]+len[c[k][3]]]%MOD1+hs1[1][c[k][2]]*b1s[len[c[k][3]]]%MOD1)%MOD1+hs1[1][c[k][3]])%MOD1 == hs2[1] && ((hs1[2][c[k][1]]*b2s[len[c[k][2]]+len[c[k][3]]]%MOD2+hs1[2][c[k][2]]*b2s[len[c[k][3]]]%MOD2)%MOD2+hs1[2][c[k][3]])%MOD2 == hs2[2]){ puts("YES"); for(int l=1;l<=3;++l){ if(c[k][l]==1){ for(int m=1;m<=len[1];++m){ putchar(a[m]); } } else if(c[k][l]==2){ for(int m=len[1]+1,mm=1;mm<=len[2];++m,++mm){ putchar(a[m]); } } else{ for(int m=len[1]+len[2]+1,mm=1;mm<=len[3];++m,++mm){ putchar(a[m]); } } puts(""); } return 0; } } } } puts("NO"); return 0; }
【枚举】【字符串哈希】Gym - 101164K - Cutting
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。