LCS
这题列一个二维表格,明白状态是如何转移过来的
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
typedef long long LL;
const int N = 3030;
char a[N], b[N], res[N];
int ne[N], f[N][N];
int main()
{
scanf ("%s %s", a + 1, b + 1);
int n = strlen(a + 1), m = strlen(b + 1);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (a[i] == b[j])
f[i][j] = max(f[i][j] , f[i - 1][j - 1] + 1);
}
int i = n, j = m;
while (f[i][j])
if (a[i] == b[j]) res[f[i --][j --]] = a[i]; // 如果两个字符相等,代表f[i][j]是由f[i - 1][j - 1]转移过来的
else
{ // 若两个字符不相等,则寻找是f[i - 1][j] or f[i][j - 1]转移过来的(此时不需要记录答案)
if (f[i][j] == f[i - 1][j]) i --;
else j --;
}
printf ("%s", res + 1);
return 0;
}