TOPCODE - The Top-Code

no tags 

A word is a string of two or more letters while a code is a string of one or more distinct words in lexicographic order. Thus a string of letters may represent either a word or a code. An optimum code is a code that contains the maximum number of words.

For a given string of letters there may be one or more optimum codes. The optimum code of top priority is the optimum code that appears at the top when all optimum codes are arranged in lexicographic order.

Given a string of letters, you are required to write a program that finds the following:

  • The total number of words, m in an optimum code,
  • The total number of optimum codes, n represented by the string,
  • The optimum code of top priority, the top-code.

Input 

Input consists of multiple test cases.

For each test case there is only one line of input. It contains a string of at most 100 letters.

A line consisting of a single letter terminates input.

Output 

For each test case, present output in two lines.

The first line gives the two integers m and n defined above. The next line gives the optimum code of top priority, the top-code.

Sample Input 

aaaaaa
words
lexicographic
a

Sample Output 

2 1
aa aaaa
1 1
words
3 2
lexic og raphic


Kanpur-Kolkata 2004-2005


hide comments
Wilmer Bandres: 2013-05-12 19:10:57

I got TL using O(N^3) and i have to make the algorithm run in O(N^2)

Last edit: 2013-05-12 19:11:11
:D: 2011-08-11 23:03:40

I did it in O(N^2) but the time wasn't all that impressive.

David Gómez: 2010-01-03 07:38:14

I got AC using a O(N ^ 3) algorithm

Adrian Jaskó³ka: 2009-12-20 01:14:36

i have O(n^3) algorithm and TL. what's expected complexity for this problem?

Last edit: 2009-12-20 01:38:10

Added by:Duc
Date:2008-12-09
Time limit:0.165s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Kanpur 2004