【C++】ZZ1848- 解题精讲
【Horn Coding Studio】CPP编程专栏题目
题目描述
给N个单词串，和一个文章串，求每个单词串是否是文章串的子串，并求每个单词在文章中出现的次数。 文章串长度S： N个单词串总长T：输入
第一行一个整数表示N。 第二行一个字符串表示文章串S。 接下来N行每行一个字符串表示单词串。输出
输出N行，第i行表示第i个单词串出现的次数。样例输入 [url=http://dis.qidao1
23.com/]复制
2
sdabcad
dab
a样例输出 [url=http://dis.qidao1
23.com/]复制
1
2提示
来源
一点即通
这道题乍一看……【C++】ZZ1847- 解题精讲 - 冯子坤 - 博客园 (cnblogs.com)再多几次询问不就完事了吗！
然后……T了！
其实一看就不难发现，旧hash算法for在这里至少先要循环500次，再加上至少100000的字符串长度，后果可想而知……（小知识，1s最多可跑完o（1e8）的内容）
https://img2022.cnblogs.com/blog/2729601/202206/2729601-20220625220648702-251715497.png
这里至少有9个蛋了，另外体量还是1e9*5，自然干不过这道题，不过，我们可以在旧的hash上做一些改动，使其变得简便，不tle
因此…………我还没有想出来……
代码
ZZOJ TLE
#include using namespace std;const int p=13131;const long long mod=1e9+7;char s1,s2;long long hash1,hash2,pre;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
页:
[1]