Under construction

Still being built. Things may change

Buzzwords

Time limit1sMemory limit128 MB

Summary
For each line, strip spaces and report the highest occurrence count among substrings of length 1, 2, 3, and so on, stopping at the first length where no substring repeats.
Level

Medium5 of 10

Topics
String, Hash map, Implementation, String matching
Solved
No attempts yet

Problem

The word THE is the most common three-letter word. It even appears inside other words, such as "other" and "mathematics", and it can hide split across two words, such as "not here". Have you ever wondered which words of lengths other than three are the most common?

You are given a text. Ignore every space, so that each line becomes one run of uppercase letters, and call any kk consecutive letters of that run a word of length kk (words may overlap). First, among all words of length 11, take one that occurs most often; if it occurs more than once, output the number of occurrences. Then do the same for words of length 22, 33, and so on, stopping once you reach a length at which no word occurs more than once.

Input

The input is a sequence of lines. The last line is empty and must not be processed. Every line except the last contains at least 11 and at most 10001000 characters, each of which is an uppercase letter or a space; the spaces are irrelevant and must be ignored.

Output

For each input line, print one number per line: the number of occurrences for words of length 11, then length 22, then 33, and so on. When you reach a length at which no word repeats, print a single blank line, print nothing further for that input line, and move on to the next line.

Examples1

  1. Example 1

    Input
    OTHER MATHEMATICS NOT HERE
    AA
    
    
    Expected output
    4
    3
    3
    2
    2
    
    2