uva 11081 - Strings(LCS)

题目链接：11081 - Strings

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

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

仿照http://www.cnblogs.com/yuzhaoxin/archive/2012/05/04/2483259.html

#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;

}