Processing math: 0%

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

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

时间限制:1000MS      内存限制:524288KB

出题人:zzx          难度:6.0

  • 题目描述

给定字符串 s 。你需要回答 n 个询问,第 i 个询问给出一个正整数 k_i 和一个字符串 m_i,请求出 s 的所有子串 t 中,满足 m_it 中出现至少 k_i 次的字符串 t 的长度的最小值。

一个字符串的子串是该字符串中的连续一段字符。

保证任意两个询问的 m_i 不相同。

  • 输入格式

第一行包含一个字符串 s1 \leq \left|s\right| \leq 10^5)。

第二行包含一个正整数 n1 \leq n \leq 10^5)。

接下来 n 行,每行一个正整数 k_i1 \leq k_i \leq \left|s\right|)和一个非空字符串 m_i,表示第 i 个询问。

所有字符串仅包含小写英文字母,且所有询问字符串的总长度不超过 10^5

  • 输出格式

对于每个字符串输出一行表示答案。

如果 m_is 中出现次数小于 k_i,输出 -1 。…