1.给出两个字符串，求出这样的一个最长的公共子序列的长度最长的公共子序列：子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。
算法1：递归
设两个字符串分别是
char str1[MAXL]; 长度是len1
char str2[MAXL]; 长度是len2
设f(str1,len1,str2,len2)为str1和str2的最大公共子串的长度，则可以对两个字符串的最后一个字符的情况进行枚举：
情况一：str1[len1-1] == str2[len1-1]，则f(str1,len1,str2,len2) = 1+ f(str1,len1-1,str2,len2-1)
情况二：str1[len1-1] != str2[len1-1]，则f(str1,len1,str2,len2) = max(f(str1,len1-1,str2,len2),f(str1,len1,str2,len2-1))
程序如下：
#include <iostream> using namespace std;
#include <string.h>
#define MAX 1000
char str1[MAX], str2[MAX];
int commonstr(int,int);
void main(){
while(cin>> str1 >> str2){
intlen1=strlen(str1);
intlen2=strlen(str2);
cout<<commonstr(len1-1,len2-1);
cout<<endl;
}
}
int commonstr(int len1,int len2){
if(len1==-1 || len2==-1) return 0;
if(str1[len1]==str2[len2])
return 1+commonstr(len1-1,len2-1);
else{
int tmp1=commonstr(len1-1,len2);
int tmp2=commonstr(len1,len2-1);
if(tmp1>tmp2)
return tmp1;
else
return tmp2;
}
}
算法2：动态规划
输入两个子串s1,s2,设MaxLen(i, j)表示: s1的左边i个字符形成的子串，与s2左边的j个字符形成的子串的最长公共子序列的长度MaxLen(i, j) 就是本题的“状态”，定义一数组
假定len1 = strlen(s1),len2 = strlen(s2）那么题目就是要求MaxLen(len1,len2)
显然：
MaxLen(n,0) = 0 ( n= 0…len1）
MaxLen(0,n) = 0 ( n=0…len2）
递推公式：
if ( s1[i-1] == s2[j-1] )
MaxLen(i,j) = MaxLen(i-1,j-1) + 1;
else
MaxLen(i,j) = Max(MaxLen(i,j-1), MaxLen(i-1,j) );
#include <iostream> using namespace std;
#include <string.h>
char sz1[1000];
char sz2[1000];
int anMaxLen[1000][1000];
int main()
{
while( cin >> sz1 >> sz2 ) {
int nLength1 = strlen( sz1);
int nLength2 = strlen( sz2);
int nTmp;
int i,j;
for( i = 0;i <= nLength1; i ++ )
anMaxLen[i][0] = 0;
for( j = 0;j <= nLength2; j ++ )
anMaxLen[0][j] = 0;
for( i = 1;i <= nLength1;i ++ ) {
for( j = 1; j <= nLength2; j ++ ) {
if( sz1[i-1] == sz2[j-1] )
anMaxLen[i][j] =
anMaxLen[i-1][j-1] + 1;
else {
int nLen1 = anMaxLen[i][j-1];
int nLen2 = anMaxLen[i-1][j];
if( nLen1 > nLen2 )
anMaxLen[i][j] = nLen1;
else
anMaxLen[i][j] = nLen2;
}
}
}
cout << anMaxLen[nLength1][nLength2] << endl;
}
}