思路：
可以对t字符串进行一次操作：将第一个字符放到最后面，那么假设操作若干次后得到一个新的字符串t，若存在一个字符串a，若新的t与字符串a的一共子串可以匹配的化，那么称t和a循环同构。 而本题就是求t字符串与目标字符串有多少个循环同构
首先：可以将t字符串的第一个字符放到最后面，那么就相当于一共环，那么就可以将这个环进行破环成链的操作，也就是开一个原t字符串里两倍的数组，存储破环成链后的操作
求一个字符串与另一个字符串是否匹配，那么可以用哈希函数进行解决
先预处理t字符串的哈希函数，然后不断枚举t数组，将每一个长度为原t字符串的长度存储下来
//预处理t
void init(int len)
{
p[0] = 1,h[0] = 1;
for(int i = 1;i<=2 * len;i++)
{
p[i] = p[i- 1] * P;
h[i] = h[i - 1] * P + str[i];
}
}
//存储每个T字符串长度的子串的哈希值
ULL get(int l,int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
for(int i = 1;i<=len;i++)
{
ha.push_back(get(i,i + len - 1));
}之后还要对存储的每个T字符串长度的子串的哈希值的数组进行排序，因为要对其进行二分查找答案
其次，在处理目标字符串，过程同上：
//预处理目标字符串的哈希函数
void init1(int len)
{
p[0] = 1,h1[0] = 1;
for(int i = 1;i<= len;i++)
{
h1[i] = h1[i - 1] * P + s[i];
}
}
这里不用存储长度为len的子串的哈希值，因为可以直接通过一个函数得到与循环同构的子串长度相同的子串
ULL get1(int l,int r)
{
return h1[r] - h1[l - 1] * p[r - l + 1];
}
最后把每个T字符串长度的子串的哈希值，通过二分查找，看存储每个T字符串长度的子串的哈希值的数组中是否存在，存在cnt++;（查找的是在目标字符串中的T字符串长度的子串）
bool check(int l,int r)
{
ULL x = get1(l,r);
ULL idx = lower_bound(ha.begin() , ha.end(),x) - ha.begin();
if(idx == ha.size()) return false;
else return ha[idx] == x;
}
for(int i = 1;i + len - 1 <= len1;i++)
{
if(check(i,i + len - 1)) cnt++;
}
最后AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e7 + 10,P = 131; //N为1e6 + 10时候会段错误，所以N为1e7 + 10
ULL h[N],h1[N],p[N]; //两个哈希函数和一个p进制数组，p进制数组存储的是每一个字符串转化为p进制的数
char s[N],str[N]; //一个是t字符串，一个是要查询的字符串
int n; //查询的次数
vector<ULL> ha; //存储t字符串中的每一个循环同构字符串
//h[N]是t字符串的哈希值，h1[N]是要查询的字符串的存储的哈希值
void init(int len) //对t字符串进行初始化
{
p[0] = 1,h[0] = 1;
for(int i = 1;i<=2 * len;i++) //因为是t的循环同构字符串，所以t字符串在相当于一个环，那么 //就破环成链。破环后的t字符串的长度是原长度的2倍
{
p[i] = p[i- 1] * P; //转换为p进制
h[i] = h[i - 1] * P + str[i]; //存储哈希值
}
}
//对要查询的字符串进制初始化
void init1(int len)
{
p[0] = 1,h1[0] = 1;
for(int i = 1;i<= len;i++)
{
h1[i] = h1[i - 1] * P + s[i];
}
}
//求t字符串的循环同构的哈希值
ULL get(int l,int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
//求要查询的字符串的子串（长度为原t字符串的长度）的哈希值
ULL get1(int l,int r)
{
return h1[r] - h1[l - 1] * p[r - l + 1];
}
//检查 查询的字符串的子串的哈希值是否在t字符串的哈希值中出现过
bool check(int l,int r)
{
ULL x = get1(l,r);
//得到要查询的字符串的子串（长度为原t字符串的长度）的哈希值
ULL idx = lower_bound(ha.begin() , ha.end(),x) - ha.begin();
//loer_biund()返回的是一个迭代器，但将返回的值 - ha.begin()那么可以近似的看为返回的是下标
//lower_bound() 是一个二分查找函数，用于在已排序的序列中查找第一个不小于（即大于或等于）给定
//值的元素。它返回该元素的迭代器。如果序列中所有元素都小于给定值，则返回尾后迭代器（即
//end()）。
if(idx == ha.size()) return false;
//因为如果没有查询到返回的是hash.end()，所以只要判断返回值是不是为ha.size()
else return ha[idx] == x;
//lower_bound() 找的是 大于或等于x的元素，而本提是t的循环同构于要查询的字符串的子串匹配，所
//以当两者相等是返回true
}
int main()
{
cin >>str + 1 >> n; //从1开始存储
int len = strlen(str + 1);
for(int i = 1;i<=len;i++) str[i + len] = str[i]; //对t数组破环成链
init(len); //对t字符串进行哈希存储
for(int i = 1;i<=len;i++)
{
ha.push_back(get(i,i + len - 1)); //存储t字符串所有的循环同构字符串
}
sort(ha.begin() ,ha.end() ); //因为要用到二分查询，所以要排序
while(n --)
{
int cnt = 0; //有多少个子串可以匹配
cin >>s + 1;
int len1 = strlen(s + 1);
init1(len1);
for(int i = 1;i + len - 1 <= len1;i++) //枚举s字符串，i+len - 1不能超过s字符串
//的长度
{
if(check(i,i + len - 1)) cnt++; //返回true，那么可以匹配
}
cout <<cnt<<endl;
}
return 0;
}
