dx24816's blog

By dx24816, history, 6 years ago, In English

Hello,

I don't quite understand the solution for the USACO Platinum December Contest Problem 1. Can anyone explain it with more detail? Thanks!

Problem: http://usaco.org/index.php?page=viewproblem2&cpid=768

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Let's do an example:
Assume we have cow "aaab" and "abab" then we have the substrings {"a", "b", "aa", "ab", "aaa", "aab", "aaab"} for the first cow and {"a","b","ab","ba","aba","bab","abab"} for the second cow.
Unique substrings are then {"aa","aaa","aab","aaab"} for the first cow and {"ba","aba","bab","abab"} for the second cow.

First we (implicityly) generate the suffixes {"", "b", "ab", "aab", "aaab"} of first cow and {"", "b", "ab", "bab", "abab"} of the second cow and sort them together:

Suffix cow index
"" (1)
"" (2)
"aaab" (1)
"aab" (1)
"ab" (1)
"ab" (2)
"abab" (2)
"b" (1)
"b" (2)
"bab" (2)

Now for each suffix we count the number unique substrings of that suffix including its first character. Therefore we search for the previous and next suffix of another cow and calculate the length of their longest common prefix. Up to this length the substrings of this suffix are not unique.
For example "abab": the next/previous suffix of another cow is "b"/"ab" and the lengths of their longest common prefixes are 0/2. Therefore only the substrings "aba" and "abab" can be unique substrings.

Additionally one is also not allowed to count multiple occurrences within a word multiple times. Therefore also the length of the longest common prefix of the previous suffix belonging to the same cow is relevant as substrings up to that length are already counted at that suffix.
for example "aab": the next/previous suffix of another cow is "ab"/"" and the lengths of their longest common prefixes are 1/0. Therefore the substrings "aa" and "aab" could be unique substrings but the string "aa" is already counted during the calculation of "aaab". To avoid this double counting we also evaluate the length of the longest common prefix with previous suffix of same cow which is 2 in this case. Therefore only the substring "aab" is a new unique substring.

Here is the list of the length of longest common prefix(lcp) of previous suffix of same cow, previous suffix of other cow and next suffix of other cow. The number of new unique substrings is then the length of the suffix minus the maximal lcp value.

Suffix cow index lcp's (prev. same/prev. other/next other) new unique substrings
"" (1) -/-/0 0
"" (2) -/0/0 0
"aaab" (1) 0/0/1 3
"aab" (1) 2/0/1 1
"ab" (1) 1/0/2 0
"ab" (2) 0/2/0 0
"abab" (2) 2/2/0 2
"b" (1) 0/0/1 0
"b" (2) 0/1/- 0
"bab" (2) 1/1/- 2

Therefore we have (3+1)=4 unique substrings for the first cow and (2+2)=4 unique strings for second cow, which confirms the sizes of the sets.