题解 AT2418 【共通部分文字列】
TRZ_2007
2020-12-09 19:09:22
# Description
给你两个字符串，要求你就它们的最长公共子序列（要求连续）。
# Solution
观察范围得到 $1\le n\le 4000$，所以 $\mathcal{O(n^2)}$ 的做法是稳稳的能过的。 但是！空间限制特别的毒瘤，所以我们需要使用 ```unsigned short``` 来卡空间，而数字肯定是存的下的，因为最长就是 $n$，且 $n < 65535$。
重点到了 $dp$，我们设 $f_{i,j}$ 表示第一个字符串到了 $i$ 的位置，第二个字符串到了 $j$ 的位置，其中 $i,j$ 必须取到。那么我们分类讨论。
- 1： $a_i \neq b_j$ 时，则当前状态无解，$f_{i,j}=0$ 。
- 2： $a_i = b_j$ 时，则当前的解为之前 1 位的长度加 1，即： $f_{i,j} = f_{i-1,j-1} + 1$ 。
对所有的 $f_{i,j}$ 取最大值就可以了。
# Code
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 4002;
unsigned short f[N][N],ans;
string a,b;
int main() {
cin >> a >> b;
a = "#" + a; b = "#" + b;
for(int i = 1;i < a.size();i++) {
for(int j = 1;j < b.size();j++) {
if(a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
ans = max(ans,f[i][j]);
}
}
cout << ans << "\n";
return 0;
}
```