记录编号	577895	评测结果	AAA
题目名称	[POJ 3461] 乌力波	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	1.356 s
提交时间	2022-12-03 10:25:33	内存使用	14.40 MiB

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long int
using namespace std;
int mod1 = 998244353;
char X[1000001], Y[10001];
int Hash1[1000001];
int power[10001];
void WORK()
{
	Hash1[0] = 0;
	scanf("%s%s", Y, X);
	int L1= strlen(Y),L2=strlen(X);
	int HS1 = 0;
	for (int i = 0; i < L1; i++)
	{
		HS1 = HS1 * 233 + (Y[i] - 'A'+1);
		HS1 %= mod1;
	}
	for (int i = 1; i <= L2; i++)
	{
		Hash1[i] = Hash1[i - 1] * 233+ (X[i - 1] - 'A' + 1);
		Hash1[i] %= mod1;
	}
	int cnt = 0;
	for (int i = 1; i <= L2-L1+1; i++)
	{
		if ((((Hash1[i + L1 - 1] - (Hash1[i - 1] * power[L1])) % mod1) + mod1) % mod1 == HS1)
		{
				cnt++;
		}
	}
	printf("%lld\n", cnt);
}
signed main()
{
	freopen("oulipo.in", "r", stdin);
	freopen("oulipo.out", "w", stdout);
	int T;
	power[0] = 1;
	for (int i = 1; i <= 10000; i++)
	{
		power[i] = power[i - 1] * 233;
		power[i] %= mod1;
	}
	cin >> T;
	while (T--)
	{
		WORK();
	}
	return 0;
}