YZOJ P3750 [校内训练20180529]字符串的频度
时间限制：1000MS 内存限制：524288KB
出题人：zzx 难度：\(6.0\)
-
题目描述
给定字符串 \(s\) 。你需要回答 \(n\) 个询问，第 \(i\) 个询问给出一个正整数 \(k_i\) 和一个字符串 \(m_i\)，请求出 \(s\) 的所有子串 \(t\) 中，满足 \(m_i\) 在 \(t\) 中出现至少 \(k_i\) 次的字符串 \(t\) 的长度的最小值。
一个字符串的子串是该字符串中的连续一段字符。
保证任意两个询问的 \(m_i\) 不相同。
-
输入格式
第一行包含一个字符串 \(s\)（\(1 \leq \left|s\right| \leq 10^5\)）。
第二行包含一个正整数 \(n\)（\(1 \leq n \leq 10^5\)）。
接下来 \(n\) 行，每行一个正整数 \(k_i\)（\(1 \leq k_i \leq \left|s\right|\)）和一个非空字符串 \(m_i\)，表示第 \(i\) 个询问。
所有字符串仅包含小写英文字母，且所有询问字符串的总长度不超过 \(10^5\) 。
-
输出格式
对于每个字符串输出一行表示答案。
如果 \(m_i\) 在 \(s\) 中出现次数小于 \(k_i\)，输出 \(-1\) 。
-
样例输入
|
1 2 3 4 5 6 7 8 9 |
abbb 7 4 b 1 ab 3 bb 1 abb 2 bbb 1 a 2 abbb |
-
样例输出
|
1 2 3 4 5 6 7 |
-1 2 -1 3 -1 1 -1 |
-
子任务
| 测试点编号 | \(|s|\) | \(n\) | 约定 |
|---|---|---|---|
| 1-3 | \(\le 300\) | \(\le 300\) | 无 |
| 4-5 | \(\le 5000\) | \(\le 5000\) | |
| 6-7 | \(\le 100000\) | \(\le 100000\) | 字符串 \(s\) 仅包含字符 a |
| 8-10 | \(\le 50000\) | \(\le 50000\) | 每个 \(m_i\) 在 \(s\) 中出现次数不超过 \(50\) |
| 11-12 | \(\le 100000\) | \(\le 100000\) | |
| 13-16 | \(\le 50000\) | \(\le 50000\) | 所有 \(m_i\) 的总长不超过 \(50000\) |
| 17-20 | \(\le 100000\) | \(\le 100000\) | 无 |
题解的做法：
将所有的匹配串建一个 AC自动机，然后母串放在上面跑，经过的点计入下当前母串所匹配到的位置，用 fail指针在树上启发式合并，对树上所有的匹配串的终止点计算答案，计算答案是与匹配串在母串出现次数线性相关的。
证明该算法总复杂度是 \(O(nlog^2n+n\sqrt n)\)
复杂度的关键在于证明 所有匹配串在母串出现次数之和 范围有保证。
题目中保证任意的串 \(m_i\) 均不相同，所以长度大于 \(\sqrt n\) 最多只能出现 \(\sqrt n\) 次，长度小于 \(\sqrt n\) 的 \(s\) 的子串在母串出现次数之和最多就 \(n\sqrt n\)，所以所有匹配串在母串出现次数之和为 \(O(n\sqrt n)\) 。
首先建 AC自动机是肯定的，但是我们有一个很好的 动态 线性表： std::vector<> ！！！
所以匹配到一个串就暴力插到 std::vector<> 里，最后在里面暴力找。
时空复杂度 \(O(n\sqrt n)\) 。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <vector> #define _min(_a_,_b_) ((_a_)<(_b_)?(_a_):(_b_)) inline int getnum() { register char c=getchar(); while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } template<class T> inline void getstr(char s[],T&ls) { register char c=0; while(!(c>='a' && c<='z')) c=getchar(); ls=0; while(c>='a' && c<='z') s[++ls]=c,c=getchar(); s[ls+1]=0; return; } int cnt,ch[105050][26],endidx[105050]; inline void insertStr(char s[],register int ls,const int&idx) { register int now=0; for(register int i=1;i<=ls;i++) { register short c=s[i]-'a'; if(!ch[now][c]) ch[now][c]=++cnt; now=ch[now][c]; } endidx[now]=idx; } int fail[105050]; inline void build() { static int lst[105050]; register int front=0,rear=0; for(register int j=0;j<26;j++) if(ch[0][j]) lst[rear++]=ch[0][j],fail[ch[0][j]]=0; while(front<rear) { register int now=lst[front++]; for(register int j=0;j<26;j++) if(ch[now][j]) fail[ch[now][j]]=ch[fail[now]][j],lst[rear++]=ch[now][j]; else ch[now][j]=ch[fail[now]][j]; } } char s[105050],m[105050]; unsigned lm[105050],k[105050]; std::vector<int>endpos[100001]; int main() { int ls;getstr(s,ls); register int N=getnum(); for(register int i=1;i<=N;i++) { k[i]=getnum(); getstr(m,lm[i]); insertStr(m,lm[i],i); } build(); register int now=0; for(register int i=1;i<=ls;i++) { register short c=s[i]-'a'; now=ch[now][c]; for(register int j=now;j;j=fail[j]) if(endidx[j]) endpos[endidx[j]].push_back(i); } for(register int i=1;i<=N;i++) { if(endpos[i].size() < k[i]) { printf("%d\n",-1); continue; } register unsigned mlen=UINT_MAX; for(register unsigned j=k[i];j<=endpos[i].size();j++) mlen=_min(mlen,endpos[i][j-1]-(endpos[i][j-1-k[i]+1]-lm[i]+1)+1); printf("%u\n",mlen); } return 0; } |