NC15253. 白兔的字符串
描述
白兔有一个字符串T。白云有若干个字符串S1,S2..Sn。
白兔想知道，对于白云的每一个字符串，它有多少个子串是和T循环同构的。
提示：对于一个字符串a，每次把a的第一个字符移动到最后一个，如果操作若干次后能够得到字符串b，则a和b循环同构。
所有字符都是小写英文字母
输入描述
第一行一个字符串T（|T|<=10^6）
第二行一个正整数n (n<=1000)
接下来n行为S1~Sn (|S1|+|S2|+…+|Sn|<=10^7)，max(|S1|,|S2|,|S3|,|S4|,..|Sn|)<=10^6
输出描述
输出n行表示每个串的答案
示例1
输入:
abab 2 abababab ababcbaba
输出:
5 2
C++14(g++5.4) 解法, 执行用时: 402ms, 内存消耗: 58372K, 提交时间: 2020-09-01 15:19:27
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
const int p=123;
int ha[N],a=1;
char s[N];
unordered_map<int,bool> unp;
int main()
{
int b;
scanf("%s%d",s+1,&b);
int len=strlen(s+1);
for(int i=1;i<=len;i++)
a*=p;
for(int i=1;i<=len*2;i++){
ha[i]=ha[i-1]*p+s[i];
if(i>=len) unp[ha[i]-ha[i-len]*a]=true,s[i+1]=s[i+1-len];
}
while(b--){
scanf("%s",s+1);
int len1=strlen(s+1),sum=0;
for(int i=1;i<=len1;i++){
ha[i]=ha[i-1]*p+s[i];
if(i>=len&&unp[ha[i]-ha[i-len]*a]) sum++;
}
printf("%d\n",sum);
}
}
C++(clang++ 11.0.1) 解法, 执行用时: 879ms, 内存消耗: 109940K, 提交时间: 2022-08-16 16:02:12
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 2000007,P=131;
map<ull,int>mp;
int n,m,min1;
ull h[N],p[N];
string s,t;
ull get(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
int main() {
cin>>s>>n;
int ls = s.size();
p[0] = 1;
s=' '+ s+s;
for(int i= 1;i<N;++i)p[i]=p[i-1]*P;
for(int i=1;i<=ls*2;++i){
h[i+1]=h[i]*P+s[i];
if(i>=ls)mp[get(i-ls+1,i)]=1;
}
while(n--){
cin>>t;
int cnt = 0;
for(int i = 0;i<t.size();++i)h[i+1]=h[i]*P+t[i];
for(int i=ls;i<=t.size();++i)cnt+=mp.count(get(i-ls+1,i));
cout<<cnt<<endl;
}
return 0;
}