提示: 欢迎访问OurACM平台。
Problem 1670 Word Repetitions

Accept: 21    Submit: 39
Time Limit: 3000 mSec    Memory Limit : 65536 KB

Problem Description

Give you a word string, what you want to do is to find the longest substring that is repeated two or more times in the word string.

Input

There are multiply test cases. For each test case, the first line is a word string S, the length of the string S will not be longer than 1000000 and only contains capital letters A-Z.

Output

For each test case, output the longest substring of S that appears more than one times repeated in S and the number of appearance of the substring in S. Separate them by a single space.
If there is more than one substring of maximum length that is repeated, you should output the least substring according to the lexicographic order.
If there is no repetition in S, just output “No Found!” .

Sample Input

BACCADA BACCACA ABABABA CDTTDEDCDTTDED ABC AABBCC ABABA

Sample Output

A 3 AC 2 ABABA 2 CDTTDED 2 No Found! A 2 ABA 2

Hint

A naive algorithm might not be sufficient to solve this problem.

Source

FOJ月赛-2008年11月

Submit  Back  Status  Discuss