链接：

文章目录

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

白兔有一个字符串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

题解：

hash题
好久没打都忘得差不多了
讲哈希的博客
根据题意，我们可以得知，要寻找与T是循环同构的子串
那T也就相当于是环，我们拆环为链，长度加倍，
然后将二倍的T中每一部分取哈希，每一部分的长度就是原T的长度
然后根据大小进行排序
输入子串a后，因为是在中取连续子串，所以本身就是一条链，我们按照T的长度对a的每一部分取hash然后比较是否相等
比较大小的方法可以用二分查找，因为我们之前已经对大小进行排序了；也可以模拟map，直接用map会超时

代码：

因为我的代码写太乱了，找了大佬条理清晰的代码。
并加上详细注释（应该很详细了 ）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + 5;
ull hs[maxn];
ull base[maxn]; 
char T[maxn<<1],s[maxn];
int n;
vector<ull> v;
ull gethash(int i,int j){
   //获得子串的hash 
    return hs[j]-hs[i-1]*base[j-i+1];
}
//查找
bool judge(int i,int j){
   
    ull x=gethash(i,j);//获得子串的hash 
    int id=lower_bound(v.begin(),v.end(),x)-v.begin();//二分查找 
    if(id==v.size())return false;//如果没找到 
    else return v[id]==x;//判断是否找到 
}
int main(){
   
    base[0]=1;
    for(int i=1;i<maxn;i++)
        base[i]=base[i-1]*131;
    cin>>(T+1);
    ll len=strlen(T+1);

    for(int i=1;i<=len;i++)
        T[i+len]=T[i];//拆环为链，长度加倍 
        
    for(int i=1;i<=2*len;i++)
        hs[i]=hs[i-1]*131+(T[i] - 'a' + 1);//对链进行hash 
        
    for(int i=1;i<=len;i++)
        v.push_back(gethash(i,i+len-1));//获得子串的hash 
    
	sort(v.begin(),v.end());//对哈希结果进行排序 ，方便后面的二分查找 
    
	cin>>n;
    while(n--){
   
        cin>>(s+1);
        ll lens=strlen(s+1);
        int cnt=0;
        
        for(int i=1;i<=lens;i++)
            hs[i]=hs[i-1]*131+(s[i] - 'a' + 1);//进行hash 
            
        for(int i=1;i+len-1<=lens;i++)
            if(judge(i,i+len-1))cnt++;//判断子串是否与T循环同构 
        cout<<cnt<<endl;
    }
    return 0;
}