算法-最长公共子串

算法-字符串

1 最长公共子串

简介

在两个字符串中,找到最长公共子串(Longest Common Subsequence)的长度.
即最长的相同的一段的长度

演示

字符串A: “abcjerryzrfdef”
字符串B: “ajerryzrfbcdefgh”

它们的最长公共子串的长度为8.

演示解析

字符串A: “abcjerryzrfde”
字符串B: “ajerryzrfb”

他们的最长公共子串为”jerryzrf”.

实现

Version 1 (暴力枚举)

暴力枚举yyds

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int GetLCSLength(string &strA, string &strB)
{
int lengthA = strA.length();
int lengthB = strB.length();
int length = 0; //公共子串长度
int MaxLength = 0; //最长公共子串长度
for(int i = 0; i < lengthA; i++)
{
for(int j = 0; j < lengthB; j++)
{
while(strA[i] == strB[j] && i < lengthA && j < lengthB) //找到公共子序列
{
i++;
j++;
length++;
}
MaxLength = max(length, MaxLength); //更新最长公共子串长度
length = 0; //公共子串长度归零
}
}
return MaxLength;
}

可以看到这种暴力枚举的性能在大量数据情况下很差,时间复杂度大概为O(lengthA * lengthB),接下来我们用上另一种算法.

Version 2 (数组矩阵)

求最长公共子串长度,就是求字符串A和字符串B中最长重复的地方的长度,于是我们可以摆出字符串A和字符串B,把它们放在矩阵中,相同的地方为true,否则为false.

字符串A: “abcjerryzrfde”
字符串B: “ajerryzrfb”
   a b c  j e r  r  y z r  f
a 1 0 0 0 0 0 0 0 0 0 0
j 0 0 0 1 0 0 0 0 0 0 0
e 0 0 0 0 1 0 0 0 0 0 0
r 0 0 0 0 0 1 1 0 0 1 1
r 0 0 0 0 0 1 1 0 0 1 1
y 0 0 0 0 0 0 0 1 0 0 0
z 0 0 0 0 0 0 0 0 1 0 0
r 0 0 0 0 0 0 0 0 0 1 0
f 0 0 0 0 0 0 0 0 0 0 1
b 0 1 0 0 0 0 0 0 0 0 0

从中我们可以发现,公共子串就是一条斜线.
所以我们可以写一个函数,求出每一条斜线中连续部分的长度,其中最长的长度,即为最长公共子串的长度

当我们计算最长连续斜线长度时,我们就会发现一个问题:如何表示当前计算的是哪一条斜线?
这时候我们就把对角线看作 0 ,左下的是负数,右上的是正数

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//在(lengthA * lengthB)的矩阵中,获取从 k 开始的斜线长度
int GetObliqueLength(bool matrix[][100001], int lengthA, int lengthB, int k)
{
//初始化
bool ObliqueLine[100001]; //斜线
int cnt = 0; //斜线长度
int x, y; //开始的(x, y)坐标

if (k < 0) //在左下部分
{
x = -k;
y = 0;
} else { //在右上部分或为对角线
x = 0;
y = k;
}
//获取斜线
while (x < lengthA && y < lengthB)
{
ObliqueLine[cnt++] = matrix[x++][y++];
}
//计算最长连续斜线长度
int length = 0; //连续斜线长度
int MaxLength = 0; //最长连续斜线长度
for (int i = 0; i < cnt; i++)
{
if (ObliqueLine[i] == false) //不连续
{
MaxLength = max(length, MaxLength); //更新最长连续斜线长度
length = 0; //连续斜线长度归零
continue;
}
length++; //连续斜线长度增加
}
return max(length, MaxLength); //返回最长连续斜线长度
}

//获取最长公共子串的长度
//Longest Common Subsequence
int GetLCSLength(string &strA, string &strB)
{
int lengthA = strA.length();
int lengthB = strB.length();
//转换为矩阵
bool matrix[lengthA][100001];
for (int i = 0; i < lengthA; i++)
{
for(int j = 0; j < lengthB; j++)
{
matrix[i][j] = strA[i] == strB[j];
}
}
//找到最长连续斜线
int max = 0;
for (int i = -lengthA + 1; i < lengthB; i++)
{
int length = GetObliqueLength(matrix, lengthA, lengthB, i);
max = (length > max) ? length : max;
}
return max;
}

该版本用的是数组写的,可能有点丑,接下来是一个用vector写的.

Version 3 (vector矩阵)

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//在(lengthA * lengthB)的矩阵中,获取从 k 开始的斜线长度
int GetObliqueLength(vector<vector<bool>> &matrix, int k)
{
//初始化
vector<bool> ObliqueLine; //斜线
int cnt = 0; //斜线长度
int x, y; //开始的(x, y)坐标
if(k < 0) //在左下部分
{
x = -k;
y = 0;
}else{ //在右上部分或为对角线
x = 0;
y = k;
}
//获取斜线
while(x < matrix.size() && y < matrix[0].size())
{
ObliqueLine.push_back(matrix[x++][y++]);
}
//计算最长连续斜线长度
int length = 0; //连续斜线长度
int MaxLength = 0; //最长连续斜线长度
for(vector<bool>::iterator it = ObliqueLine.begin(); it != ObliqueLine.end(); it++)
{
if(*it == false) //不连续
{
MaxLength = max(length, MaxLength); //更新最长连续斜线长度
length = 0; //连续斜线长度归零
continue;
}
length++; //连续斜线长度增加
}
return max(length, MaxLength); //返回最长连续斜线长度
}

//获取最长公共子串的长度
//Longest Common Subsequence
int GetLCSLength(string &strA, string &strB)
{
int lengthA = strA.length();
int lengthB = strB.length();
//转换为矩阵
vector<vector<bool>> matrix(lengthA, vector<bool>(lengthB, false));
for(int i = 0; i < lengthA; i++)
{
for(int j = 0; j < lengthB; j++)
{
matrix[i][j] = strA[i] == strB[j];
}
}
//找到最长连续斜线
int max = 0;
for(int i = -lengthA + 1; i < lengthB; i++)
{
int length = GetObliqueLength(matrix, i);
max = (length > max) ? length : max;
}
return max;
}

别忘了

1
#include <vector>

END

本文就到这里了,接下来你可以自己写一个函数,求出最长公共子串和其长度.
暴力枚举yyds!