TopCoder problem "StringTrain" used in SRM 161 (Division II Level Two)



Problem Statement

    You will be given a String[] cars containing a list of strings that will participate in the Train. The Train is a string that will be built using the given strings. The building process works as follows:
  • Train is initialized to the value of the 0th element of cars
  • For each element of cars in order, beginning with element 1, check if some proper prefix of the current element matches some proper suffix of the Train. If so, append the element of cars to the Train, not repeating the matched prefix. If more than one proper prefix matches, take the longest. If no proper prefix matches, the current element of cars is not appended.
A prefix of a string is a substring that starts at the beginning of the string. A proper prefix is a prefix that has positive length, and is not the entire string. A suffix of a string is a substring that terminates at the end of the string. A proper suffix is a suffix that has positive length, and is not the entire string.



Once you have built the Train, remove all but the last occurrence of each character in the Train. For example, if the Train was (quotes for clarity) "abbbcabdb" you would be left with "cadb". You will return a string of the form "n x" where, n is the length of the Train before removing all but the last occurrence of each character, and x is the string after the removal. n and x are separated by exactly one space, the return should not have any leading or trailing whitespace, and n should have no leading zeros.
 

Definition

    
Class:StringTrain
Method:buildTrain
Parameters:String[]
Returns:String
Method signature:String buildTrain(String[] cars)
(be sure your method is public)
    
 

Constraints

-cars will contain between 2 and 50 elements inclusive
-Each element of cars will contain between 1 and 50 uppercase letters inclusive
 

Examples

0)
    
{"ABCDE","CDFFF","CDE","CDEGG","GABC"}
Returns: "10 DEGABC"
The Train begins as (quotes for clarity) "ABCDE". Element 1 of cars cannot be added since it doesn't match any suffix of the Train. Element 2 of cars cannot be added since the only matching prefix is the entire string. Element 3 can be added, and the resulting Train is "ABCDEGG". Element 4 can also be added, and the resulting Train is "ABCDEGGABC". After removing all but the last occurrence of each character we are left with "DEGABC".
1)
    
{"AAAAA","AAAAA","AAAAA"}
Returns: "7 A"
The Train begins as "AAAAA". The longest matching proper prefix of element 1 of cars is "AAAA" so the resulting Train is "AAAAAA". The longest matching proper prefix of element 1 of cars is "AAAA" so the resulting Train is "AAAAAAA". After removing all but the last occurrence of each character, the result is "A".
2)
    
{"CABABDABAB","CABAB","ABABDABAB","DABAB"}
Returns: "15 CDAB"
3)
    
{"ABABAB","ABABAB","ABABABAB","BZZZZZ"}
Returns: "15 ABZ"
4)
    
{"A","A","A","AA"}
Returns: "1 A"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1801

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4610&pm=1801

Writer:

brett1479

Testers:

Problem categories:

String Manipulation