问题 A: 串串香
时间限制: 1 Sec 内存限制: 512 MB
题面
题面谢绝公开。
题解
吃字符串可海星……正解KMP,然而我就是用hash水过233333。
直接串内匹配,看是否能拆成更小的字符串。从小到大枚举长度,不是约数直接跳过,是约数再匹配。
预处理一个hash前缀和直接搞就完了。
代码:
#include<bits/stdc++.h> #define int long long #define rint register int #define ull unsigned long long using namespace std; const int Z=2333; int T,n,m,ans,len,blo; ull hs[1000006],JZ[1000006]; char ch[1000006]; bool _ok; signed main() { // freopen("ex_ccx2.in","r",stdin); // freopen("my.out","w",stdout); scanf("%lld",&T); while(T--) { scanf("%lld %lld %s",&n,&m,ch+1);JZ[0]=1; if(m==1){printf("%lld\n",n-1);continue;} bool te=1; for(rint i=1;i<=m;++i) { hs[i]=hs[i-1]*Z+(ch[i]-'A'+1); if(ch[i]!='A')te=0; JZ[i]=JZ[i-1]*Z; } if(te){printf("%lld\n",n*m-1);continue;} if(n*m<=1000000) { ans=0;JZ[0]=1; for(rint i=1;i<=n;++i) for(rint j=1;j<=m;++j) { rint lin=(i-1)*m+j; hs[lin]=hs[lin-1]*Z+(ch[j]-'A'+1); JZ[lin]=JZ[lin-1]*Z; } for(rint i=1;i<n*m;++i) if(hs[i]==hs[n*m]-hs[n*m-i]*JZ[i])ans=i; printf("%lld\n",ans); continue; } len=0,blo=0; for(rint i=1;i<=(m/2);++i) { if(m%i!=0)continue;_ok=1; for(rint j=2;j<=(m/i);++j) if((hs[i*(j-1)]-hs[i*(j-2)]*JZ[i])!=(hs[j*i]-hs[i*(j-1)]*JZ[i])){_ok=0;break;} if(_ok){len=i,blo=m/len;break;} } printf("%lld\n",(n-1)*m+(blo-1)*len); } return 0; }