CommonSubsequence

TCCC07 Sponsor 4 · 2007-07-30 · by Mike Mirzayanov

TCCC07 Sponsor 4 · 2007-07-30 · by Mike Mirzayanov · Simple Search, Iteration

Show categories

Class Name: CommonSubsequence

Return Type: String

Method Name: maxLex

Arg Types: (vector<string>, vector<string>, int)

Problem Statement

A subsequence of a string s is a string that can be obtained by erasing zero or more characters from s. For example, "aacb", "c", "", and "abacaba" are subsequences of "abacaba", but "bbc" is not.

Common subsequences of strings s₁ and s₂ are strings that are subsequences of both s₁ and s₂.

A string s₁ is called a cyclic shift of string s if s₁ can be obtained by removing zero or more characters from the beginning of string s and appending them to the end of string s in the same order. For example, strings "abcde", "bcdea" and "eabcd" are cyclic shifts of string "abcde", but "cdeba" is not.

You are given two String[]s a and b. Construct a string A by concatenating all the elements of a, and construct a string B by concatening all the elements of b.

Consider all common subsequences for all pairs (x, y), where x is any cyclic shift of string A, and y is any cyclic shift of string B. There are length(A) * length(B) such pairs. Find the common subsequence among all of these that comes last alphabetically, and return the last suffixLength characters of that subsequence. If the subsequence contains less than suffixLength characters, then return the whole subsequence.

Constraints

a and b will each contain between 1 and 50 elements, inclusive.
Each element of a and b will contain between 1 and 50 characters, inclusive.
Each element of a and b will contain only characters with ASCII value between 35 and 126, inclusive.
suffixLength will be between 1 and 100, inclusive.

Examples

{"baab"}
{"aaabb"}
10
Returns: "bbaa"

The answer is the one of the common subsequences for the pair ("bbaa", "bbaaa").

{"a", "cb"}
{"bc", "a"}
100
Returns: "cb"

The answer is one of the common subsequences for the pair ("acb", "cab") (there exist more such pairs).

{"xzzzzzzzzzzzzzzzzzzx"}
{"xxxxzzzzzzzzzzz"}
10
Returns: "zzzzzzzzxx"

{"ichhbca", "aghafbbgbaehi"}
{"jdhccgeiaaijbddh"}
6
Returns: "iihhge"

{"ccceeaeedbafadbaaeacafdd", "eddadb", "abfeccaffbabeaafcbccecf", "ddbdcebdfcddedacfabefdaeccbdcbdafefaeccfaa", "ffddb"}
{"cceaaadbdfecdfcabffcecbddcfbbfcdebaeafe", "accab", "ece", "afadefabaaeacbfdfbdeecfcabdedededdebcfcdbbfbaebfed", "faa"}
100
Returns: "fffffffffffffffeeeedb"

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

Coding Area

Language: C++17 · define a public class CommonSubsequence with a public method string maxLex(vector<string> a, vector<string> b, int suffixLength) · 128 test cases · 2 s / 256 MB per case