Description：

给一个模板串和多个询问串，求模板串有多少个子串可以由询问串循环得到。

$1\leqslant n\leqslant 10^5$

Solution：

建出模板串的 $SAM$ ，把询问串倍长，然后把询问串在模板串上跑，同时记录匹配长度，然后如果长度够长就累加答案，注意如果长度过长需要跳父亲，也就是说除了刚开始那 $n-1$ 个位置其他的时候都要保证 $n$ 正好落在这个点上，循环同构的话就在后缀自动机节点上打 $vis$ 表示，如果经过多次只统计一次。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 2000010

char c[MAXN];

struct node

{

	int tr[26];

	int par,maxl;

}s[MAXN];

int ptr = 1,root = 1,last = 1;

int newnode(int l){int k = ++ptr;s[k].maxl = l;return k;}

int siz[MAXN];

void extend(int k)

{

	int p = last;

	int np = newnode(s[p].maxl + 1);

	++siz[np];

	for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

	if(p == 0)s[np].par = root;

	else

	{

		int q = s[p].tr[k];

		if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

		else

		{

			int nq = newnode(s[p].maxl + 1);

			memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

			s[nq].par = s[q].par;

			s[q].par = s[np].par = nq;

			for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

		}

	}

	last = np;

	return;

}

int w[MAXN],p[MAXN];

int vis[MAXN],tim = 0;

int main()

{

	scanf("%s",c + 1);

	n = strlen(c + 1);

	for(int i = 1;i <= n;++i)extend(c[i] - 'a');

	for(int i = 1;i <= ptr;++i)++w[s[i].maxl];

	for(int i = 1;i <= n;++i)w[i] += w[i - 1];

	for(int i = ptr;i >= 1;--i)p[w[s[i].maxl]--] = i;

	for(int i = ptr;i >= 1;--i)

	{

		int k = p[i];

		siz[s[k].par] += siz[k];

	}

	scanf("%d",&m);

	for(int i = 1;i <= m;++i)

	{

		scanf("%s",c + 1);

		int l = strlen(c + 1);

		for(int i = l + 1;i < 2 * l;++i)c[i] = c[i - l];

		++tim;

		int cur = root,matchlen = 0;

		int ans = 0;

		for(int i = 1;i < 2 * l;++i)

		{

			if(s[cur].tr[c[i] - 'a'] != 0)

			{

				++matchlen;

				cur = s[cur].tr[c[i] - 'a'];

			}

			else

			{

				while(cur && s[cur].tr[c[i] - 'a'] == 0)

				{

					cur = s[cur].par;

					matchlen = s[cur].maxl;

				}

				if(s[cur].tr[c[i] - 'a'] != 0)

				{

					++matchlen;

					cur = s[cur].tr[c[i] - 'a'];

				}

			}

			while(matchlen > l && s[s[cur].par].maxl >= l)cur = s[cur].par;

			if(matchlen >= l && vis[cur] != tim)

			{

				ans += siz[cur];

				vis[cur] = tim;

			}

		}

		cout << ans << endl;

	}

	return 0;

}