PROBLEM STATEMENT
A string X is an ordered superstring of the vector words if
Each element of words is a substring of X.
There exists a sequence of indices x_1 <= x_2 <= ... <= x_n, where n is the number of elements
in words. For each element k of words, where k is a 1-based index, there is an occurrence of
words[k] that starts at the x_k-th letter of X.
For example "abca" is an ordered superstring of {"abc", "ca"}, but "cabc" is not.
Given a vector words, return the length of its shortest ordered superstring.
DEFINITION
Class:OrderedSuperString
Method:getLength
Parameters:vector
Returns:int
Method signature:int getLength(vector words)
CONSTRAINTS
-words will contain between 1 and 50 elements, inclusive.
-Each element of words will contain between 1 and 50 lowercase letters ('a'-'z'), inclusive.
EXAMPLES
0)
{"abc","ca"}
Returns: 4
This is the example from the problem statement. The shortest ordered superstring is "abca". The
sequence of indices is {0, 2}. There is an occurrence of "abc" starting at character 0 of "abca",
and there is an occurrence of "ca" starting at character 2 of "abca".
1)
{"a","a","b","a"}
Returns: 3
Although the given words are all substrings of "ab", they do not appear in the proper order. The
shortest ordered superstring is "aba".
2)
{"abcdef", "ab","bc", "de","ef"}
Returns: 6
3)
{"ab","bc", "de","ef","abcdef"}
Returns: 12
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.