uva 11081 - Strings(LCS)

题目大意：给出三个字符串，从分别从第一个字符串和第二个字符串中挑选子串a,b，用a和b组成第三个字符串的子串c，问可组成的子串有多少种。

解题思路：说起来惭愧啊，题目一点思路没有，题目老早就看了，今天查了题解，愣是想了一晚上，终于想清楚一点点了，dp[i][j][k]表是用s1中的前i个字符和s2中的前j个字符的子串组成s3前k个字符的子串的情况。

#include <stdio.h>  
#include <string.h>  
const int N = 70;  
const int tmp = 10007;  
  
int dp[N][N][N], dp1[N][N][N], dp2[N][N][N];  
char s1[N], s2[N], s3[N];  
  
int solve() {  
    int len1 = strlen(s1 + 1);  
    int len2 = strlen(s2 + 1);  
    int len3 = strlen(s3 + 1);  
    memset(dp, 0, sizeof(dp));  
    memset(dp1, 0, sizeof(dp1));  
    memset(dp2, 0, sizeof(dp2));  
  
    for (int i = 0; i <= len1; i++)  
       for (int j = 0; j <= len2; j++)  
            dp[i][j][0] = dp1[i][j][0] = dp2[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) {  
                    dp1[i][j][k] = dp1[i - 1][j][k];  
                    if (s1[i] == s3[k])  
                        dp1[i][j][k] += dp[i - 1][j][k - 1];  
                    dp1[i][j][k] %= tmp;  
                }  
                if (j) {  
                    dp2[i][j][k] = dp2[i][j - 1][k];  
                    if (s2[j] == s3[k])  
                        dp2[i][j][k] += dp[i][j - 1][k - 1];  
                    dp2[i][j][k] %= tmp;  
                }  
                dp[i][j][k] = (dp1[i][j][k] + dp2[i][j][k]) % tmp;  
            }  
        }  
    }  
    return dp[len1][len2][len3];  
}  
  
int main() {  
    int cas;  
    scanf("%d",&cas);  
    while (cas--) {  
        scanf("%s%s%s", s1 + 1, s2 + 1, s3 + 1);  
        printf("%d\n", solve());  
    }  
    return 0;  
}

补充：软件开发 , C++ ,