Blog

JerryZRF的Blog

算法-最长公共子串

发表于 更新于 分类于

算法-字符串

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!