5415：CRB and Substrings

题目描述

Value of a string is defined as the number of distinct substrings of it.
For example, value of “ab” is 3(“a”, “b”, “ab”), and value of “xyx” is 5(“x”, “y”, “xy”, “yx”, “xyx”).
Now CRB has a string s.
For some integer $k$, CRB wants to know $k$-length substring of $s$ which has maximum value. But it seems not so easy. Can you help him?

输入解释

There are multiple test cases.
The first line contains a string $s$. The next line contains an integer $Q$ denoting the number of queries. Each of the next $Q$ lines contains a single integer $k$.
1 ≤ $|s|$ ≤ $10^{5}$
$s$ consists only of lowercase English letters.
1 ≤ $Q$ ≤ 10
1 ≤ $k$ ≤ $|s|$

输出解释

For each query $k$, output the string whose value is maximum among all $k$-length substrings of $s$, followed by its value.
If multiple substrings have same maximum value, output the lexicographically smallest one.

输入样例

baa
2
2
1

输出样例

ba 3
a 1

提示

Query 1:
2-length substrings are “ba” and “aa”.
Value of “ba” is 3, and value of “aa” is 2.
Query 2:
1-length substrings are “b” and “a”.
Both have value 1, but “a” is lexicographically smaller.

来自杭电HDUOJ的附加信息

Author	KUT（DPRK）
Recommend	wange2014

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2015 Multi-University Training Contest 10

源链接： HDU-5415

最后修改于 2020-10-25T23:22:28+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
6000/3000MS(Java/Others)	131072/131072K(Java/Others)