Given 3 strings of only lowercase letter you have to count the number of ways you can construct the third string by combining two subsequences from the first two strings.
After deleting 0 or more characters from a string we can get its subsequence. For example “a”, “b”, “c”, “ab”, “ac”, “bc” and “abc” all the strings are the subsequences of “abc”. A subsequence may also be empty.
Now suppose there are two subsequences “abc” and “de”. By combining them you can get the following strings “abcde”, “abdce”, “abdec”, “adbce”, “adbec”, “adebc”, “dabce”, “dabec”, “daebc” and “deabc”.
Input
The first line of the input contains a single integer T (0 Output For each test case output a single integer denoting the number of ways you can construct the third string from the first two string by the above way. The result may be very large. You should output the result%10007.
2 abc abc abc abbcd bccde abcde 8 18
Sample Input Output for Sample Input
Problemsetter: Abdullah-al-Mahmud
Special Thanks: Md. Kamruzzaman
s1串,s2串得到s3串的方法:
#include#include #include #include #include typedef long long LL; using namespace std; const int MOD=10007; int f[70][70][70],f1[70][70][70],f2[70][70][70]; char s1[70],s2[70],s3[70]; int main() { int t; cin>>t; while(t--) { cin>>s1+1>>s2+1>>s3+1; memset(f,0,sizeof(f)); memset(f1,0,sizeof(f1)); memset(f2,0,sizeof(f2)); int len1=strlen(s1+1); int len2=strlen(s2+1); int len3=strlen(s3+1); for(int i=0;i<=len1;i++) { for(int j=0;j<=len2;j++) f[i][j][0]=f1[i][j][0]=f2[i][j][0]=1; } for(int k=1;k<=len3;k++) { for(int i=0;i<=len1;i++) { for(int j=0;j<=len2;j++) { if(i) { f1[i][j][k]=f1[i-1][j][k]; if(s1[i]==s3[k]) f1[i][j][k]+=f[i-1][j][k-1]; } if(j) { f2[i][j][k]=f2[i][j-1][k]; if(s2[j]==s3[k]) f2[i][j][k]+=f[i][j-1][k-1]; } f[i][j][k]=(f1[i][j][k]+f2[i][j][k])%MOD; } } } cout<