题解 | #白兔的字符串#

#include <bits/stdc++.h>

using namespace std;
#define ULL unsigned long long
#define P 131

const int N = 1e6 + 10;
ULL h[N], p[N];
char s[2 * N];
char s1[N];
ULL h1[N], p1[N];

ULL get_hash(int l, int r)
{
	return h[r] - h[l - 1] * p[r - l + 1];
}

ULL get_hash_d(int l, int r)
{
	return h1[r] - h1[l - 1] * p1[r - l + 1];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> s + 1;
	int len = strlen(s + 1);

	for (int i = 1; i <= len; i ++) s[i + len] = s[i];

	h[0] = 1, p[0] = 1;
	for (int i = 1; i <= len * 2; i ++ )
	{
		p[i] = p[i - 1] * P;
		h[i] = h[i - 1] * P + s[i]; 
	}

	unordered_set<ULL> jset;
	for (int i = len; i <= 2 * len; i ++ )
	{
		ULL v = get_hash(i - len + 1, i);
		jset.insert(v);
	}

	int m;
	cin >> m;
	while (m --)
	{
		cin >> s1 + 1;
		int len1 = strlen(s1 + 1);
		h1[0] = 1, p1[0] = 1;
		for (int i = 1; i <= len1; i ++)
		{
			h1[i] = h1[i - 1] * P + s1[i];
			p1[i] = p1[i - 1] * P;
		}
		int ans = 0;

		for (int i = len; i <= len1; i ++ )
		{
			ULL v = get_hash_d(i - len + 1, i);
			if (jset.count(v)) ans ++;
		}
		cout << ans << "\n";
	}
	return 0;
}