本文由编程笔记#小编为大家整理，主要介绍了题解Oulipo相关的知识，希望对你有一定的参考价值。
给出两个串S1，S2（只有大写字母），求S1在S2中出现了多少次。
例如：S1=“ABA”，S2=“ABABA”，答案为2。
输入T组数据，对每组数据输出结果。
输入输出格式
输入格式
第一行为T，表示有T组数据。
接下来分别为每组数据的两个串S1，S2。
输出格式
T行，分别输出每组数据中S1在S2中出现的次数。
每组数据保证S1长度≤104">10^4，S2长度≤106">10^6。
输入输出样例
输入样例
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
104">106">题解104">106"> 字符串hash裸题（用kmp貌似会麻烦一些）.
104">106"> 子串可以重复，所以直接遍历一遍就可以得出答案104">106">。
#include <iostream>
#include
#include
#define MAX_N 10000
#define MAX_M 1000000
using namespace std;
int t;
int n, m;
char s1[MAX_N | 1], s2[MAX_M | 1];
unsigned long long h1[MAX_N | 1], h2[MAX_M | 1];
unsigned long long p[MAX_N | 1];
inline void Insert(char s[], int len, unsigned long long h[])
{
h[0] = s[0] - ‘A‘;
for(register int i = 1; i i)
{
h[i] = h[i - 1] * 26 + s[i] - ‘A‘;
}
return;
}
int main()
{
scanf("%d", &t);
p[0] = 1;
for(register int i = 1; i <= MAX_N; ++i)
{
p[i] = p[i - 1] * 26;
}
while(t--)
{
scanf("%s%s", s1, s2);
n = strlen(s1);
m = strlen(s2);
if(n > m)
{
printf("0
");
continue;
}
Insert(s1, n, h1);
Insert(s2, m, h2);
int ans = 0;
if(h1[n - 1] == h2[n - 1])
{
++ans;
}
for(register int i = 1; i + n <= m; ++i)
{
if(h1[n - 1] == h2[i + n - 1] - h2[i - 1] * p[n])
{
++ans;
}
}
printf("%d
", ans);
}
return 0;
}
京公网安备 11010802041100号