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\) 。
-
输出格式
对于每个字符串输出一行表示答案。