next up previous
Next: Line Interval Density Up: UMD HPC98 Questions Previous: UMD HPC98 Questions

Maximum Repeating Substring

You must find a substring of an input string, such that the substring consecutively repeats the most number of times.

A string s is said to be a substring of string t if the characters of s appear consecutively in order within t. For example, ``BAT'' is a substring of ``ACROBATS'' since these characters occur in the same order as follows ``ACROBATS''.

A substring repeats consecutively if it appears multiple times in a string, with no gaps between its occurrences. For example, the string ``BLAAABADBADX" has two repeating substrings: 'A', which repeats three times, and 'BAD', which repeats twice. The answer reported is '3', since the length of the repeating substring is not considered. Only consecutive repetitions of a substring are counted, so the last two occurrences of 'A' don't count toward the total number of repetitions.

Input format

The input will be a single line of text containing the input string. Assume the longest string will be 50 characters.

Output format

Output ``Maximum repeat: " and the maximum number of times a substring is consecutively repeated.





Maximum repeat: 3




Maximum repeat: 4

Test data used in judging

Input 1 Output 1
Input 2 Output 2
Input 3 Output 3
Input 4 Output 4

Our solution

Chau-Wen Tseng
Tue Mar 24 16:22:12 EST 1998