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$ 。

• 样例输入

• 样例输出

• 子任务

测试点编号	$|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)$ 。