TopCoder problem "FourSubstrings" used in TCO07 Round 4 (Division I Level Three)



Problem Statement

    

You are given a String[] text. Concatenate all elements of text to make one string. You are also given four Strings a, b, c and d, all of which are substrings of the concatenated text. Find exactly one occurrence of each of these four strings in the text (they are allowed to overlap). Each character in the text that belongs to one or more of these substring occurrences is called covered. For example, if the text is "foursubstrings", and a = "our", b = "s", c = "ring", and d = "sub", one possible configuration is:

foursubstrings - text
 our           - a
    s          - b
         ring  - c
    sub        - d
 ++++++  ++++  - covered letters

The letters marked by '+' are covered.

Return a int[] containing exactly two elements. The first element should be the minimum possible number of covered characters in a configuration, and the second element should be the maximum possible number of covered characters.

 

Definition

    
Class:FourSubstrings
Method:getCoverageCount
Parameters:String[], String, String, String, String
Returns:int[]
Method signature:int[] getCoverageCount(String[] text, String a, String b, String c, String d)
(be sure your method is public)
    
 

Constraints

-text will contain between 1 and 50 elements, inclusive.
-Each element of text will contain between 1 and 50 characters, inclusive.
-text will contain only lowercase letters ('a'-'z').
-a, b, c and d will each contain between 1 and 50 characters, inclusive.
-a, b, c and d will contain only lowercase letters ('a'-'z').
-a, b, c and d will each be a substring of the concatenation of text.
 

Examples

0)
    
{"abacaba"}
"ab"
"ba"
"a"
"c"
Returns: {4, 6 }
The minimal number of covered characters corresponds to "ABACaba", and the maximal corresponds to "ABACaBA" (the covered characters are shown in uppercase).
1)
    
{"hello"}
"he"
"l"
"l"
"o"
Returns: {4, 5 }
Occurrences of substrings may overlap.
2)
    
{"ababababa", "baba"}
"ababababa"
"ababababa"
"ababababa"
"ababababa"
Returns: {9, 13 }
3)
    
{"foursubstrings"}
"our"
"s"
"ring"
"sub"
Returns: {10, 11 }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10759&pm=7668

Writer:

Mike Mirzayanov

Testers:

PabloGilberto , brett1479 , radeye , Olexiy

Problem categories:

Simple Search, Iteration