问题
最长公共子串(Longest Common Substring)问题，对与给定的两个字符串，求它们的最长公共子串，注意：子串是连续的。
暴力方法
遍历每一个子串，进行比较，一个长度为$n$的字符串拥有$n^2$个子串，所以该方法的复杂度为$O(n^4)$。
动态规划
把问题分解的若干个子问题求解，开一个$n×n$的数组存以当前位置结尾的最长公共子串，dp[i][j]表示字符串1的第i位与字符串2的第j位结尾的最长子串。
$$
dp[i][j]=\begin{cases}
0,str1[i]!=str2[j]\\
dp[i-1][j-1]+1,str1[i]=str2[j]
\end{cases}
$$
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
33
34
35
36
37
38
|
#include<bits/stdc++.h>
using namespace std;
string s1, s2;
const int maxn = 1e4 + 5;
int dp[maxn][maxn], maxlen;
int main() {
while (cin >> s1 >> s2) {
int len1 = s1.length(), len2 = s2.length();
maxlen = 0;
for (int i = 0; i <= len1; i++) {
dp[i][0] = 0;
}
for (int i = 0; i <= len2; i++) {
dp[0][i] = 0;
}
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
if (s1[i] == s2[j]) {
dp[i + 1][j + 1] = dp[i][j] + 1;
}
else {
if (dp[i][j] > maxlen) {
maxlen = dp[i][j];
}
dp[i + 1][j + 1] = 0;
}
}
if (dp[i][len2] > maxlen) {
maxlen = dp[i][len2];
}
}
if (dp[len1][len2] > maxlen) {
maxlen = dp[len1][len2];
}
cout << maxlen << "\n";
}
}
|
问题扩展（最长公共子序列）
- 公共子序列问题比子串问题要简单一些，因为最后最大值就存在dp数组的最后一个位置，不需要通过其他方法获取
- 状态转移方程如下：
$$
dp[i][j]=\begin{cases}
max(dp[i-1][j],dp[i][j-1]),str1[i]!=str2[j]\\
dp[i-1][j-1]+1,str1[i]=str2[j]
\end{cases}
$$
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
|
#include<bits/stdc++.h>
using namespace std;
string s1, s2;
const int maxn = 1e4 + 5;
int dp[maxn][maxn], maxlen;
int main() {
while (cin >> s1 >> s2) {
int len1 = s1.length(), len2 = s2.length();
maxlen = 0;
for (int i = 0; i <= len1; i++) {
dp[i][0] = 0;
}
for (int i = 0; i <= len2; i++) {
dp[0][i] = 0;
}
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
if (s1[i] == s2[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[len1][len2] << "\n";
}
}
|
return 0;
本文链接：
https://luojinrong.github.io/2019/05/16/最长公共子串-LCS/
