1 /* 2 题意：T组测试，每行三个串，求 用前两个串的一些子串（可以是空）有多少种方式可以拼成第三个串。 3 4 参考了 http://blog.csdn.net/u012997373/article/details/38762393?utm_source=tuicool&utm_medium=referral 5 6 用三个三维数组 。 7 f[i][j][k] 表示 拼到第三个串的第 K 个字符时，用到了第一个串的前 i 个字符， 第二个串的前 j 个字符。 8 但是第 K 个字符的来源有两个地方，s1 和 s2， 9 所以用 f1[i][j][k]表示第 K 个字符来自 s1 串，f2 同理表示来自 s2 串 。 10 辣么最后 f[i][j][k] = f1[i][j][k] + f2[i][j][k] ； 11 12 考虑到空串，初始化时 f[i][j][0] = f1[i][j][0] = f2[i][j][0] = 1 ； 13 */ 14 15 16 17 #include<cstdio> 18 #include<cstring> 19 #include<algorithm> 20 using namespace std; 21 const int maxn=65; 22 const int MOD=10007; 23 int f[maxn][maxn][maxn],f1[maxn][maxn][maxn],f2[maxn][maxn][maxn]; 24 char a[maxn],b[maxn],c[maxn]; 25 int main() 26 { 27 int t; 28 scanf("%d",&t); 29 while(t--) 30 { 31 scanf("%s%s%s",a,b,c); 32 int la=strlen(a); 33 int lb=strlen(b); 34 int lc=strlen(c); 35 memset(f1,0,sizeof(f1)); 36 memset(f2,0,sizeof(f2)); 37 memset(f,0,sizeof(f)); 38 for(int i=0;i<=la;i++) 39 for(int j=0;j<=lb;j++) 40 { 41 f[i][j][0]=1; 42 f1[i][j][0]=1; 43 f2[i][j][0]=1; 44 } 45 for(int k=1;k<=lc;k++) 46 { 47 for(int i=0;i<=la;i++) 48 { 49 for(int j=0;j<=lb;j++) 50 { 51 if(i) 52 { 53 f1[i][j][k] = f1[i-1][j][k]; 54 if(c[k-1] == a[i-1]) 55 f1[i][j][k] = (f1[i][j][k] + f[i-1][j][k-1] ) % MOD; 56 } 57 if(j) 58 { 59 f2[i][j][k] = f2[i][j-1][k]; 60 if(c[k-1] == b[j-1]) 61 f2[i][j][k] = ( f2[i][j][k] + f[i][j-1][k-1] ) % MOD; 62 } 63 f[i][j][k] = (f1[i][j][k] + f2[i][j][k]) % MOD; 64 } 65 } 66 } 67 printf("%d ",f[la][lb][lc]); 68 } 69 return 0; 70 }