题解
哈希真的是个好东西,在O(N)预处理之后,能在O(1)的时间内枚举任意子串.
这道题我们可以考虑对每种字母进行哈希.
具体来讲,hash1[i][c]存储的是字母c的哈希值(位置)
这样处理之后,就在S串里面枚举长度为T串的子串,再枚举两种字母,如果26个字母哈希值能够相等,那么这样的变化是没问题的
时间复杂度 O(N\times 26\times 26)
这里进制为131,模数为 2^{64}
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<iostream> #include<cstdio> using namespace std; typedef long long ll; const ll p=131; const int N=210000; int n,m; char sr1[N],sr2[N]; unsigned long long hash1[N][28],hash2[N][28],Q[N]; int Ans[N],ans; int main(){ int i,j,k,x,y; cin>>n>>m; scanf("%s%s",sr1+1,sr2+1); Q[0]=1; for(i=1;i<=n;++i) Q[i]=Q[i-1]*p; for(j=0;j<=25;++j) for(i=1;i<=n;++i){ hash1[i][j]=hash1[i-1][j]*p; if(sr1[i]-'a'==j)hash1[i][j]+=1; } for(j=0;j<=25;++j) for(i=1;i<=m;++i){ hash2[i][j]=hash2[i-1][j]*p; if(sr2[i]-'a'==j)hash2[i][j]+=1; } int cnt; for(i=1;i<=n-m+1;++i){ cnt=0; for(x=0;x<26;++x){ if(cnt!=x)break; for(y=0;y<26;++y) if(hash2[m][x]==hash1[i+m-1][y]-hash1[i-1][y]*Q[m]) if(hash2[m][y]==hash1[i+m-1][x]-hash1[i-1][x]*Q[m]){ cnt++; break; } } if(cnt==26) Ans[++ans]=i; } cout<<ans<<endl; for(i=1;i<ans;++i)printf("%d ",Ans[i]); if(ans!=0)printf("%d",Ans[ans]); } |