复试上机准备之最长公共子串

题目要求

求 2 个字符串的最长公共子串(输出时不包含空格),字符串长度不超过 255。

输入:

What’re your namess?

My namess are your.

输出:

reyour

namess

分析

最长公共子串/序列,是动态规划中一个非常经典的题型。但我之前接触的是最长公共子序列,子序列不要求序列的元素是相邻的,而子串需要元素是相邻的。

暴力法

两个循环,把序列 B 的每个元素开始的子串和 A 的所有元素进行比较,找出所有子串,从而找出最长子串。

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
void get_sub_str(string a, string b) {
int len_a = a.length();
int len_b = b.length();

int start = 0, max_len = 0;

for (int i = 0; i < len_a; ++i) {
for (int j = 0; j < len_b; ++j) {
// 当找到相等的时候就顺着比下去,直到不相同
// 这里重新使用了一个变量 k,就不用改 i、j 了
if (a[i] == b[j]) {
int k = 1;
while (i + k < len_a && j + k < len_b && (a[i + k] == b[j + k])) {
++k;
}
if (k > max_len) {
start = i;
max_len = k;
}
}
}
}

for (int i = start; i < start + max_len; ++i) {
cout << a[i];
}
cout << endl;
}

不过上面这种实现只能输出第一个最长的子串,如果要输出所有最长子串,就要把所有有可能成为最长子串的子串保存下来,输出的时候再进行判断,只输出长度是最长的那些子串。

动态规划-空间换时间

我们可以用 m * n 的矩阵来存放相等的信息,如果 arr[m][n] != 0 则表明 a[m] == b[n],子串就是斜对角线这些元素都不为零的那些位置。因此只用找最长的斜线即可。

为了简化找对角线的过程,我们可以让该点的元素值是左上方元素值加一,这样凭借元素值就知道序列的长度有多少了。

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
// 使用动态规划-空间换时间的方法
void print_sub_str(string a, string b) {
int arr[256][256] = {0};

int max_len = 0;
for (int i = 0; i < a.length(); ++i) {
for (int j = 0; j < b.length(); ++j) {
if (a[i] == b[j]) {
// 根据斜上方的元素来赋值
if (i > 0 && j > 0) {
arr[i][j] = arr[i - 1][j - 1] + 1;
}
else {
arr[i][j] = 1;
}
if (arr[i][j] > max_len) {
max_len = arr[i][j];
}
}
}
}

// 找到最有长度最长的子串
for (int i = 0; i < a.length(); ++i) {
for (int j = 0; j < b.length(); ++j) {
if (arr[i][j] == max_len) {
// 要注意这里 substr 第二个参数是子串的长度!!!而非结束位置
cout << b.substr(j - max_len + 1, max_len) << endl;
}
}
}
}

总结

无论是暴力法还是动态规划法都是有一定的技巧的。暴力法主要是注意一下变量是怎么安排的;动态规划法则要搞清楚是如何用时间换空间,如何减轻输出的计算量。