Connection Status:
Competition Arena > FourSubstrings

FourSubstrings

TCO07 Round 4 · 2007-03-07 · by Mike Mirzayanov

TCO07 Round 4 · 2007-03-07 · by Mike Mirzayanov · Simple Search, Iteration
Class Name: FourSubstrings
Return Type: int[]
Method Name: getCoverageCount
Arg Types: (vector<string>, string, string, string, string)
Problem Statement

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.

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 }
4)
{"aa"}
"a"
"a"
"aa"
"a"
Returns: {2, 2 }

Submissions are judged against all 81 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FourSubstrings with a public method vector<int> getCoverageCount(vector<string> text, string a, string b, string c, string d) · 81 test cases · 2 s / 256 MB per case

Submitting as anonymous