Repeat
InterviewTime limit1sMemory limit1024 MB
For each string, find the longest substring that appears twice without overlapping, and print its length and the earliest such substring.
- Level
Medium5 of 10
- Topics
- String, Dynamic programming, String matching
- Solved
- No attempts yet
Problem
Your teacher marks students down on essays that repeat words and phrases, when they could explore new syntax and use a thesaurus instead. To avoid being marked for repeats, you decide to check your essay for repeated substrings and find the longest one so you can fix it. Write a program that, given a string of characters, finds the greatest repeated substring with no overlapping characters.
Input
The first line contains a single integer n, the number of data sets that follow. Each data set is one line containing a string of letters of unknown length.
Output
For each data set, output the integer length of the longest repeated substring, a space, and then the repeated string. If several substrings have the same length, print the one that appears first in the string.