ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【C++】ZZ1848- 解题精讲 [打印本页]

作者: 伤心客 时间: 2022-8-13 02:15
标题: 【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]

2
sdabcad
dab
a

复制代码

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

复制代码

提示

来源

一点即通

这道题乍一看……【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

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)