可以參考: http://m.blog.csdn.net/hrn1216/article/details/51534607
給出兩個字符串,求出這樣的一個最長的公共子序列的長度:子序列中的每個字符都能在兩個原串中找到,而且每個字符的先先后順序和原串中的先后順序一致.
輸入
abcfbc abfcab
programming contest
abcd mnp
輸出
4
2
0
輸入兩個串s1,s2,設(shè)MaxLen(i,j)表示:s1的左邊i個字符形成的子串,與s2左邊的j個字符形成的子串的最長公共子序列的長度(i,j)從0開始算
MaxLen(i,j)就是本題的"狀態(tài)"
假定len1 = strlen(s1),len2 = strlen(s2)
那么題目就是要求MaxLen(len1,len2)
#include <iostream>
#include <cstring>
using namespace std;
char sz1[1000];
char sz2[1000];
int maxLen[1000][1000];
int main()
{
while(cin>>sz1>>sz2){
int length1 = strlen(sz1);
int length2 = strlen(sz2);
for(int i=0;i<length1;i++)
maxLen[i][0] = 0;
for(int j=0;j<length2;j++)
maxLen[0][j] = 0;
for(int i=1;i<=length1;i++){ //此時是數(shù)組下標,不能從0開始
for(int j=1;j<=length2;j++)
if(sz1[i-1] == sz2[j-1])
maxLen[i][j] = maxLen[i-1][j-1] + 1;
else
maxLen[i][j] = max(maxLen[i][j-1],maxLen[i-1][j]);
}
cout<<maxLen[length1][length2]<< endl;
}
return 0;
}
