练习题 No.6 最长公共子序(LCS)-附赠最长公共子串

要求

给定二个字符串 s1s2...sn 和 t1t2...tn 。求出这二个字符串最长的公共子序列的长度。
字符串 s1s2...sn 的子序列指可以表示为 Si1Si2...Sim(i1<i2<...<im) 的序列。

输入格式

第一行输入一行字符串
第二行输入一行字符串

输出格式

输出最长的长度

测试输入

bbbbaaba
aaaabbaa

测试输出

4

解题思路

使用递推式
如果str[i] == str[j]，则dp[i + 1][j + 1] = dp[i][j] + 1
否则dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
最后的dp[size][size2]即为最长子串长度
测试输入中的数据会形成以下矩阵

0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1
0 0 0 0 0 1 2 2 2
0 0 0 0 0 1 2 2 2
0 0 0 0 0 1 2 2 2
0 1 1 1 1 1 2 3 3
0 1 2 2 2 2 2 3 4
0 1 2 2 2 3 3 3 4
0 1 2 3 3 3 3 4 4

代码

#include <iostream>
#include <string>
using namespace std;

int main() {
string str;
string str2;
cin >> str;
cin >> str2;
int dp[101][101] = {0}; 
int size = str.length();
int size2 = str2.length();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size2; j++) {
if (str[i] == str2[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            } else {
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
            }
        }
    }
cout << dp[size][size2] << endl;
return 0;
}

---

#include <iostream>
#include <string>
using namespace std;

int main() {
string str;
string str2;
cin >> str;
cin >> str2;
int dp[101][101] = {0}; 
int size = str.length();
int size2 = str2.length();
    pair<int, int> max;
    max.second = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size2; j++) {
if (str[i] == str2[j]) {
if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + 1;          
                }
if (dp[i][j] > max.second) {
                    max.first = i;
                    max.second = dp[i][j];
                }
            } else {
                dp[i][j] = 0;
            }
        }
    }
for (int i = max.first - max.second + 1; i <= max.first; i++) {
cout << str[i];
    }
cout << endl;

return 0;
}