问题 B: Oulipo
问题 B: Oulipo
时间限制: 1 Sec 内存限制: 128 MB
提交: 29 解决: 20
[提交][状态][讨论版][命题人:add_lxh][Edit] [TestData]
题目链接：http://acm.ocrosoft.com/problem.php?cid=1716&pid=1
题目描述
给出两个串S1,S2(只有大写字母)，求S1在S2中出现了多少次。例如S1=“ABA”，S2=“ABABA”，答案为 2。
输入T组数据，对每组数据输出结果。
每组数据保证strlen(S1)<=10^4,strlen(S2)<=10^6。
输入
输入T,表示T组数据接下来每行一个S1,每行一个S2。
输出
输出T行，表示每组的答案。
样例输入
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN 样例输出
1
3
0 思路：用哈希函数计算母串、子串的哈希值，判断在母串中一个个加字母并一个个减字母后的哈希值是否和子串的哈希值相等。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
map<char, int>letter;
const int mod = 1e9+7;
int main()
{
for (int i = 1; i <= 26; i++)
{
letter[char(i + 64)] = i;//map映射，存储的是一种映射关系
//letter[a]=1,letter[b]=2,letter[c]=3……
}
int T;
cin >> T;
while (T--)
{
string child, parent;
cin >> child >> parent;
if (child.length() > parent.length())//字串比母串还长就不用比了
{
cout << 0 << endl;
}
else
{
ll hash_child = letter[child[0]];//子串哈希值初始化
ll hash_parent = letter[parent[0]];//母串哈希值初始化
ll k = 1;
for (int i = 1; i <= child.length(); i++)k *= 13;//数量级赋值给k
for (int i = 1; i < child.length(); i++)
{
hash_child = hash_child * 13 + letter[child[i]];//计算子串的哈希值
hash_parent = hash_parent * 13 + letter[parent[i]];//计算开头和子串一样长的母串的哈希值
}
//cout << hash_child << endl;
int cnt = 0;
if (hash_child == hash_parent)//开头判一判
{
cnt++;
}
for (int i = child.length(); i < parent.length(); i++)
{
//计算 母串中的子串 加上 母串中的子串下一个字母 的字符串的哈希值，然后减去 母串中的子串开头 后剩下的哈希值（要乘上数量级k）
hash_parent = hash_parent * 13 + letter[parent[i]] - letter[parent[i - child.length()]] * k;
//cout << hash_parent << endl;
if (hash_child == hash_parent)//相等则在母串匹配到了和子串一样的字符串
{
cnt++;
}
}
cout << cnt << endl;
}
}
}
