TopCoder problem "CountingCommonSubsequences" used in SRM 298 (Division I Level Three)



Problem Statement

    A subsequence of a string is obtained by removing zero or more characters from it. You are given three Strings, and must determine the number of different non-empty subsequences they all share.
 

Definition

    
Class:CountingCommonSubsequences
Method:countCommonSubsequences
Parameters:String, String, String
Returns:long
Method signature:long countCommonSubsequences(String a, String b, String c)
(be sure your method is public)
    
 

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').
 

Examples

0)
    
"call"
"accelerate"
"candle"
Returns: 6
The 6 subsequences common to all of the strings are: "c", "a", "l", "al", "ca" and "cl".
1)
    
"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.
2)
    
"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.
3)
    
"aabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabb"
"abababababababababababababababababababab"
"aaaabbbbaaaabbbbaaaabbbbaaaabbbbaaaabbbb"
Returns: 1725660

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9819&pm=6158

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , radeye , Olexiy

Problem categories:

Dynamic Programming, Recursion