字符串的题真的要比dfs,bfs的简单好多
大致思路
- 首先,再度重复哈希函数 H ( C ′ ) = H ( C , k + n ) − H ( C , k ) ∗ b n H(C')=H(C,k+n)-H(C,k)*b^n H(C′)=H(C,k+n)−H(C,k)∗bn
- 具体模板详见我的上几篇题解 哈希函数模板
- 对此题,我们只需要对字符串计算哈希函数值枚举可能的前后缀长度即可。
bool check(ull len,ull nlen){if(ahash[len]==ahash[nlen]-ahash[nlen-len]*poww[len]){return 1;}return 0;
}
while(scanf("%s",s+1)!=EOF)//两种多组输入模式//while(cin>>s+1){ahash[0]=0;int n=strlen(s+1);for(int i=1;i<=n;i++){ahash[i]=(s[i]+ahash[i-1]*b);}for(ull i=1;i<=n;i++){if(check(i,n)==1){cout<<i<<" ";}}cout<<endl;}
- 假设主串长度为N,子串长度为K,则前缀哈希值等于 h a s h [ K ] hash[K] hash[K],后缀的哈希值等于 h a s h [ N ] − h a s h [ N − K ] ∗ b K hash[N]-hash[N-K]*b^K hash[N]−hash[N−K]∗bK
- 显然,若前者等于后者,则是合法的。
AC CODE
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=1e6+9;
char s[N],s2[N];
int b=11,h=100000009,n;
ull poww[N],ahash[N];
bool check(ull len,ull nlen){if(ahash[len]==ahash[nlen]-ahash[nlen-len]*poww[len]){return 1;}return 0;
}
int main(){poww[0]=1;for(int i=1;i<=1000000;i++){poww[i]=poww[i-1]*b;}while(scanf("%s",s+1)!=EOF)//while(cin>>s+1){ahash[0]=0;int n=strlen(s+1);for(int i=1;i<=n;i++){ahash[i]=(s[i]+ahash[i-1]*b);}for(ull i=1;i<=n;i++){if(check(i,n)==1){cout<<i<<" ";}}cout<<endl;}return 0;
}