三个字符串的最长公共子序列

算法说明

这个问题是最简单的动态规划问题了，只不过是三个字符串而已。

学过动态规划的应该都知道怎么求两个字符串的最长公共子序列，很容易犯的一个错误就是：先求出前两个字符串的最长公共子序列，然后再求他和第三个字符串的最长公共子序列。举个简单的例子，三个字符串分别为abc、cab、c，前两个的最长公共子序列为ab，ab和c的公共子序列为空，实际上他们都有一个字符c，所以这种做法是错误的。

其实三个字符串的最长公共子序列的算法和两个字符串的算法是一样的，只不过存子问题的时候用的是三维数组。

代码

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
const int MAXN = 101;	//字符串的最大长度位MAXN-1
int a[MAXN][MAXN][MAXN];//a[i][j][k]表示第一个字符串的前i个字符，第二个字符串的前j个字符和
						//第三个字符串的前k个字符的最长公共子序列的长度
//函数返回三个字符串的最长公共子序列的长度
int commonLen(string strA, string strB, string strC)
{
	//n1、n2、n3分别为三个字符串的长度
	int n1 = strA.size();
	int n2 = strB.size();
	int n3 = strC.size();

	//字符串的个数可以是0-n,共n+1个可能，所以循环中是i<=n
	for(int i = 0; i <= n1; i++)
	for(int j = 0; j <= n2; j++)
	for(int k = 0; k <= n3; k++)
		if(i == 0 || j == 0 || k == 0)	//只要有一个序列的长度为0，公共子序列的长度为0
			a[i][j][k] = 0;
	//自底向上求a[i][j][k]
	for(int i = 1; i <= n1; i++)
		for(int j = 1; j <= n2; j++)
			for(int k = 1; k <= n3; k++)
			{
				if(strA[i - 1] == strB[j - 1] && strB[j - 1] == strC[k - 1])
					a[i][j][k] = a[i - 1][j - 1][k - 1] + 1;
				else 
					a[i][j][k] = max(max(a[i - 1][j][k], a[i][j - 1][k]),
									a[i][j][k -1]);
			}
	return a[n1][n2][n3];
}

int main()
{
	string str1, str2, str3;
	while(cin >> str1 >> str2 >> str3)
		cout << commonLen(str1, str2, str3) << endl;

	return 0;
}