【C++】ZZ1848- 解题精讲

【Horn Coding Studio】CPP编程专栏
题目
题目描述

给N个单词串，和一个文章串，求每个单词串是否是文章串的子串，并求每个单词在文章中出现的次数。 文章串长度S：[1,5000] N个单词串总长T：[1,1000000]输入

第一行一个整数表示N。 第二行一个字符串表示文章串S。 接下来N行每行一个字符串表示单词串。输出

输出N行，第i行表示第i个单词串出现的次数。样例输入 [url=http://dis.qidao1
23.com/]复制[/url]

1. 2
2. sdabcad
3. dab
4. a

复制代码

样例输出 [url=http://dis.qidao1
23.com/]复制[/url]

1. 1
2. 2

复制代码

提示

来源

 
一点即通

这道题乍一看……【C++】ZZ1847- 解题精讲 - 冯子坤 - 博客园 (cnblogs.com)再多几次询问不就完事了吗！
然后……T了！
其实一看就不难发现，旧hash算法for在这里至少先要循环500次，再加上至少100000的字符串长度，后果可想而知……（小知识，1s最多可跑完o（1e8）的内容）

 

 这里至少有9个蛋了，另外体量还是1e9*5，自然干不过这道题，不过，我们可以在旧的hash上做一些改动，使其变得简便，不tle
因此…………我还没有想出来……
代码

ZZOJ     TLE
[code]#include using namespace std;const int p=13131;const long long mod=1e9+7;char s1[100005],s2[100005];long long hash1[100005],hash2[100006],pre[100005];long long n;long long idx(char ch) {    return ch-'a'+1;}int main() {    scanf("%lld",&n);    scanf("%s",s1+1);    for(long long i=1; i