lcs模板.txt

北大judue上的题吗 供学习与交流用 大家一起分享 希望能好好学习

const int MAXN = 500;
short d[MAXN][MAXN];

int LCS(string a, string b , int m , int n)  //m,n分别为a,b的长度，返回最长公共子串的长度
{
	int i , j, max;
	max = m > n ? m : n;
	for (i = 0; i < max ; i ++)
	{
		d[i][0] = 0;
		d[0][i] = 0;
	}
	for (i = 0 ; i < m ; i ++)
	{
		for (j = 0 ; j < n ; j ++)
		{
			if (a[i] == b[j])
			{
				d[i+1][j+1] = d[i][j]+1;
			}
			else
			{
				d[i+1][j+1] = (d[i][j+1] > d[i+1][j])?d[i][j+1]:d[i+1][j];
			}
		}
	}
	return d[m][n];
}