白兔的字符串
白兔有一个字符串 T 。白云有若干个字符串 S_1,S_2,S_n 。
白兔想知道,对于白云的每一个字符串,它有多少个子串是和 T 循环同构的。
提示:对于一个字符串 a ,每次把 a 的第一个字符移动到最后一个,如果操作若干次后能够得到字符串 b ,则 a 和 b 循环同构。
所有字符都是小写英文字母.
首先我们分析一下,既然循环同构,那么我们可以将串 T 展开直接翻倍展开成 2|T| 的长度,然后用 Hash 保存每种 T 长度下的值,这里应该没有什么问题吧。那接下来我们在遍历一下 n 个字符串的时候顺便直接查找上面是否出现了字符串,如果有的话那么 ans++ ,至于查找的方式,用 map 的话不是一般的慢,大概是 TLE 55,(我试过了),所以我换了一个简单的方法:二分。事实证明,可以AC,然后注意一开始一定要排好序。好那么上代码:
#include<bits/stdc++.h>
using namespace std;
char ss[2000005],s[2000005];
long long ha[2000005],wei[2000005];
int base=131;
int main()
{
scanf("%s",ss);
int len=strlen(ss);
for(int i=0;i<len;i++)
ss[len+i]=ss[i];
long long hash=0,cnt=0;
wei[0]=1;
for(int i=1;i<2000005;i++)
wei[i]=wei[i-1]*base;
int num=0;
for(int i=0;i<len*2-1;i++)
{
hash=hash*base+ss[i];
cnt++;
if(cnt==len)
{
cnt--;
ha[++num]=hash;
hash=hash-wei[len-1]*ss[i-len+1];
}
}
sort(ha+1,ha+num+1);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s);
int lens=strlen(s);
int ans=0;
hash=0,cnt=0;
for(int i=0;i<lens;i++)
{
hash=hash*base+s[i];
cnt++;
if(cnt==len)
{
cnt--;
int pos=lower_bound(ha+1,ha+num+1,hash)-ha-1;
if(pos<num&&ha[pos+1]==hash)
ans++;
hash=hash-wei[len-1]*s[i-len+1];
}
}
printf("%d\n",ans);
}
return 0;
}