最长公共子序列（POJ1458)

佚名 6年前 (2019-04-21) 随笔 1375人围观抢沙发百度已收录

给出两个字符串，求出这样的一个最长的公共子序列的长度：子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。

Sample Input：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

abcfbc abfcab
programming contest
abcd mnp

Sample Output：
4
2
0

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;  4 char s1[1000];  5 char s2[1000];  6 int maxlen[1000][1000];  7 int main(void)  8 {  9     while (cin >> s1 >> s2) 10  { 11         int length1 = strlen(s1); 12         int length2 = strlen(s2); 13         int i, j; 14         for (i = 0; i <= length1 ; ++i) 15             maxlen[i][0] = 0; 16         for (i = 0; i <= length2 ; ++i) 17             maxlen[0][i] = 0; 18         for (i = 1; i <= length1 ; ++i) 19  { 20             for (j = 1; j <= length2 ; ++j) 21  { 22                 if (s1[i - 1] == s2[j - 1]) 23  { 24                     maxlen[i][j] = maxlen[i - 1][j - 1] + 1; 25  } 26                 else
27  { 28                     maxlen[i][j] = max(maxlen[i - 1][j], maxlen[i][j - 1]); 29  } 30  } 31  } 32         cout << maxlen[length1][length2]<<endl; 33  } 34     return 0; 35 }