YZOJ P3750 [校内训练20180529]字符串的频度

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)\) 。

 

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注