A5859. 「TJOI2019」甲苯先生和大中锋的字符串
编程题
省选/NOI-
知识点
题目描述
大中锋有一个长度为 $n$ 的字符串，他只知道其中的一个子串是祖上传下来的宝藏的密码。但是由于字符串很长，大中锋很难将这些子串一一尝试。
这天大中锋找到甲苯先生算命，但是甲苯先生说：「天机不可泄漏」。在大中锋的苦苦哀求下，甲苯先生告诉大中锋：「密码是在字符串中恰好出现了 $k$ 次的子串」。
但是大中锋不知道该怎么做，在大中锋再三的恳求下，甲苯先生看其真诚，又告诉他：「在恰好出现了 $k$ 次的子串中，你去按照字串的长度分类，密码就在数量最多的那一类里」。
大中锋为了尝试这个密码，想让你帮忙找出子串长度出现次数最多的长度数（如果有多个输出最长长度）。
这天大中锋找到甲苯先生算命，但是甲苯先生说：「天机不可泄漏」。在大中锋的苦苦哀求下，甲苯先生告诉大中锋：「密码是在字符串中恰好出现了 $k$ 次的子串」。
但是大中锋不知道该怎么做，在大中锋再三的恳求下，甲苯先生看其真诚，又告诉他：「在恰好出现了 $k$ 次的子串中，你去按照字串的长度分类，密码就在数量最多的那一类里」。
大中锋为了尝试这个密码，想让你帮忙找出子串长度出现次数最多的长度数（如果有多个输出最长长度）。
输入格式
第一行一个正整数 $T$，表示有 $T$ 组测试数据。
接下来 $T$ 行，每行包含一个字符串和一个正整数 $k$。
接下来 $T$ 行，每行包含一个字符串和一个正整数 $k$。
输出格式
一共输出 $T$ 行，每行一个整数表示在出现 $k$ 次的子串中出现次数的最多的长度。
如果不存在子串出现 $k$ 次，则输出 $−1$。
如果不存在子串出现 $k$ 次，则输出 $−1$。
输入输出样例
输入 #1
6 aab 1 abc 1 aaaa 2 abab 2 ababacc 2 abab 4
输出 #1
2 1 3 1 2 -1
说明/提示
对于 $20\%$ 的数据，$1 ≤ k ≤ n ≤ 10$；
对于 $100\%$ 的数据，$1 ≤ n ≤ 10^5,1 ≤ T ≤ 100,\sum n ≤ 3 \times 10^6$。
对于 $100\%$ 的数据，$1 ≤ n ≤ 10^5,1 ≤ T ≤ 100,\sum n ≤ 3 \times 10^6$。