最长公共子序列

[c++]代码库

#include <iostream>
#include <string.h>
using namespace std;
int a[100][100];
char s1[100];
char s2[100];
int main()
{   
	int len1, len2, i, j;
    cin >> s1+1 >> s2+1;
	len1=strlen(s1+1);
	len2=strlen(s2+1);
	// 两个字符串中有一个为空字符串，则最长公共子序列为0
	for(i = 0; i <= len1; i++)
        a[i][0]=0;          
	for(j = 0; j <= len2; j++)
		a[0][j]=0;
	for(i = 1; i <= len1; i++)
	 for(j = 1; j <= len2; j++)
		{
            if(s1[i]==s2[j])
			{
				a[i][j]=a[i-1][j-1]+1;
			}else
			{                //  两个字符串向后移一个字符，比较两种情况，求最大
				int length1=a[i][j-1];
				int length2=a[i-1][j];
				if(length1 > length2)
					a[i][j]=length1;
				else
					a[i][j]=length2;
			}
		}
     cout << a[len1][len2] << endl;
   return 0;

}
//2014-5-22