链接
传送门
题意
给出两个字符串\(s\)、\(t\)和整数\(k\)，在\(s\)、\(t\)中找出出现顺序相同的\(k\)段相同连续子串，输出\(k\)段子串最大长度和。
思路
与最长公共子序列类似，定义状态\(dp[i][j][k][l]\)表示\(s\)匹配到了第\(i\)个字符、\(t\)匹配到了第\(j\)个字符，当前已经匹配了\(k\)段子串，\(l\)为0时代表最后一段子串停止匹配、为1时代表最后一段子串还在匹配。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1005;
int dp[maxn][maxn][11][2];
char s[maxn], t[maxn];
int main() {
int n, m, K;
scanf("%d%d%d", &n, &m, &K);
scanf("%s%s", s + 1, t + 1);
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int k = 1; k <= K; ++k) {
if (s[i] == t[j]) {
dp[i][j][k][1] = max(dp[i - 1][j - 1][k][1], dp[i - 1][j - 1][k - 1][0]) + 1;
}
dp[i][j][k][0] = max(dp[i][j][k][1], max(dp[i - 1][j][k][0], dp[i][j - 1][k][0]));
}
ans = max(ans, dp[i][j][K][0]);
}
}
printf("%d\n", ans);
return 0;
}
|