CountingCommonSubsequences
SRM 298 · 2006-04-11 · by soul-net
Problem Statement
Notes
- A subsequence should be counted only once even if it can be obtained in more than 1 way from any of the input Strings.
Constraints
- a, b and c will have between 1 and 50 characters each, inclusive.
- Every character of a, b and c will be a lowercase letter ('a'-'z').
"call" "accelerate" "candle" Returns: 6
The 6 subsequences common to all of the strings are: "c", "a", "l", "al", "ca" and "cl".
"topcoder" "topcoder" "topcoder" Returns: 239
All possible subsequences are shared by all three strings. Note that the letter 'o' is repeated, so some of the subsequences may be formed in multiple ways. Each unique subsequence is only counted once.
"no" "correct" "answer" Returns: 0
There are many subsequences that are shared by any two of these strings, but none that are shared by all three of them.
"aabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabb" "abababababababababababababababababababab" "aaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbb" Returns: 1725660
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" Returns: 50
Submissions are judged against all 115 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CountingCommonSubsequences with a public method long long countCommonSubsequences(string a, string b, string c) · 115 test cases · 2 s / 256 MB per case