【持续更新】字符串相关算法

本文准备分享和记录一些经典字符串相关算法的实现,日后自己也可以时常翻阅查看。

我很喜欢 Python,Python 写起来像伪代码,简洁又清晰,但又是真正可以运行的代码,所以我准备都用 Python 来实现。

可能以后还会分享一些其他的算法,今天就先从字符串开始。。

一、字符串匹配/判断子串

问题描述:给定两个字符串,判断其中一个字符串是否是另一个字符串的子串。

很容易想到的一个方法就是暴力匹配,也叫作字符串匹配朴素算法。

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
mport sys


def judge_substring(str1, str2):
# 先判断哪个字符串较长
if len(str1) > len(str2):
long_str = str1
short_str = str2
else:
long_str = str2
short_str = str1

# 逐一字符比较,i 用来记录当前长字符串开始的位置,j 用来移动指针比较
i, j = 0, 0
while i < len(long_str) and j < len(short_str):
if long_str[i] == short_str[j]:
i += 1
j += 1
else:
i = i - j + 1 # i 指针回溯
j = 0

# j 走到了索引之外,表明匹配上
if j == len(short_str):
return True

return False


if __name__ == '__main__':
# 获得输入(输入两个字符串 以空格分隔)
input_strs = sys.stdin.readline().strip().split()

# 拆分为两个字符串
str1 = input_strs[0]
str2 = input_strs[1]

# 进行判断
result = judge_substring(str1, str2)

print result

先确定两个字符串哪个长哪个短,则一定是用短的那个去长的那里匹配。用两个“指针”分别记录当前从长字符串的哪个字符开始匹配,以及当前在短的字符串上匹配到了哪一个。其时间复杂度为 O(mn),m 和 n 是两个字符串的长度。

更好的办法是使用经典的 KMP算法, KMP算法通过next数组记录下当前元素失配后下一个比较的字符,而不用回溯指针,所以效率很高,时间复杂度O(m+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
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
62
63
64
65
66
67
68
69
70
71
import sys


def kmp(str1, str2):
# 先判断哪个字符串较长
if len(str1) > len(str2):
long_str = str1
short_str = str2
else:
long_str = str2
short_str = str1

# 得到 next 数组
next = get_next(short_str)

# 开始匹配
# 若当前字符匹配不上,i 指针不回溯,短字符串通过 next 数组向右滑动
i, j = 0, 0
while i < len(long_str):
if j == -1 or long_str[i] == short_str[j]:
i += 1
j += 1
else:
j = next[j]

# j 走到了索引之外,表明匹配上
if j == len(short_str):
return True

return False


def get_next(str):
# 初始化 next 数组
next = [-1 for i in range(len(str))]

# 模式串自身进行匹配
i, j = 0, -1
while i < len(str):
if j == -1 or str[i] == str[j]:

# 指针后移
i += 1
j += 1

# 防止数组越界
if i == len(str):
break

# 加上 if 判断,如果当前元素和对应的 next 元素相同,则如果向前元素失配,则对应 next 元素也一样失配,那么可以直接跳转到当前 next 元素的 next 元素
if str[i] != str[j]:
next[i] = j
else:
next[i] = next[j]

else:
j = next[j]

return next


if __name__ == '__main__':

input_strs = sys.stdin.readline().strip().split()

str1 = input_strs[0]
str2 = input_strs[1]

result = kmp(str1, str2)

print result

虽然第一种暴力匹配的最坏复杂度为O(mn),但实际执行的时间近似于O(m+n),因此仍然被广泛采用。而且 KMP 算法仅当两个字符串之间存在许多“部分匹配”的情况下才显得比暴力匹配快很多。

二、判断子序列

问题描述:给定两个字符串,判断其中一个字符串是否是另一个字符串的子序列。

子序列和子串的最大区别就是子序列可以是不连续的,但是子序列中元素的位置和原字符串中相应字符的相对位置还是要一样的。
比如字符串对于abcdefgabc是子串,adf是子序列。而bac就不是子串也不是子序列了,因为ba的相对位置与原先字符串不一样。

下面是一种比较高效的算法,只用一次循环即可判断,时间复杂度 O(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
33
34
35
36
import sys


def judge_subsequence(str1, str2):
# 先判断哪个字符串较长
if len(str1) >= len(str2):
long_str = str1
short_str = str2
else:
long_str = str2
short_str = str1

# 逐一字符比较,j 用来记录短字符串当前比较字符的位置
j = 0
for i in range(len(long_str)):
# 如果短的字符串与长字符串当前的字符匹配上,则指针后移
if long_str[i] == short_str[j]:
j += 1
# 如果短字符串到达末尾。表明已经匹配上
if j == len(short_str):
return True
return False


if __name__ == '__main__':
# 获得输入(输入两个字符串 以空格分隔)
input_strs = sys.stdin.readline().strip().split()

# 拆分为两个字符串
str1 = input_strs[0]
str2 = input_strs[1]

# 进行判断
result = judge_subsequence(str1, str2)

print result

扫描两者中长的字符串,并用一个变量 j 指向短字符串中当前比较的字符,如果 j 当前指向的字符在扫描长字符串的过程中匹配上,则 j 往后移,否则 j 不动。j 如果能移动到末尾,说明都能匹配上,且相对顺序也正确,则说明是子序列。

三、最长公共子序列

问题描述:给定两个字符串,找出两个字符串的最长公共子序列,并求得其长度。

这样的问题用暴力匹配就行不通了,因为时间复杂度太高,达到了指数级。

最长公共子序列(LCS)有最优子结构性质,定义c[i, j]表示 Xi 和 Yj 的 LCS 的长度,则可以得到如下公式:

根据上面的公式,我们可以想到用递归的方法来做,但是递归同样很慢,因为 LCS 问题还具有重叠子问题性质,递归会重复计算。

所以我们可以用动态规划的方法来解这个问题,下面是自底向上的动态规划算法,时间复杂度O(mn)

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
import sys


def find_lcs(str1, str2):
# 矩阵 c 用来记录中间结果
c = [[0 for i in range(len(str2) + 1)] for j in range(len(str1) + 1)]
# 矩阵 d 用来记录转移方向
d = [[0 for i in range(len(str2) + 1)] for j in range(len(str1) + 1)]

# 根据特征,逐行填充上述两个矩阵
for i in range(len(str1)):
for j in range(len(str2)):
if str1[i] == str2[j]:
c[i + 1][j + 1] = c[i][j] + 1
d[i + 1][j + 1] = 'ok'
else:
if c[i + 1][j] > c[i][j + 1]:
c[i + 1][j + 1] = c[i + 1][j]
d[i + 1][j + 1] = 'left'
else:
c[i + 1][j + 1] = c[i][j + 1]
d[i + 1][j + 1] = 'top'

# 回溯构造 LCS
p1, p2 = len(str1), len(str2)
lcs = ''
while c[p1][p2]:
if d[p1][p2] == 'ok': # ok 的情况下,表示此处两个字符串对应字符相等,属于 LCS
lcs += str1[p1 - 1]
p1 -= 1
p2 -= 1
elif d[p1][p2] == 'left': # 否则沿着转移方向回溯移动
p2 -= 1
elif d[p1][p2] == 'top':
p1 -= 1
lcs = lcs[::-1] # 因为是从后往前得到的 LCS,所以需要翻转字符串

return lcs


if __name__ == '__main__':

input_strs = sys.stdin.readline().strip().split()

str1 = input_strs[0]
str2 = input_strs[1]

lcs = find_lcs(str1, str2)

print lcs, len(lcs)

首先定义了两个矩阵,分别用来记录中间结果已经转移方向。然后根据性质得出的公式逐行进行计算,填充上述两个矩阵。最后根据那两个矩阵回溯得到最长公共子序列。

具体的矩阵填充图如下所示:

这个图把两个矩阵合并到了一起。我们在之前代码中定义矩阵的时候多了一行和多了一列,从这个图我们就可以看到为什么要这么做。多出来的行和列即为最左和最上面的 0 列,用来为计算的时候作为初始值。
填充完矩阵的时候,就根据转移方向矩阵从最右下角开始回溯,如果转移方向矩阵的值为 ok,则表明此时两个字符串对应位置元素相同,这个元素就属于 LCS。回溯完之后,得到的字符串即为 LCS,但因为它是从最后开始回溯的,所以还需要翻转一下,才是正确的最长公共子序列。

四、最长公共子串

问题描述:给定两个字符串,找出两个字符串的最长公共子串,并求得其长度。

最长公共子串和最长公共子序列很类似,区别就是对于中间结果矩阵,如果str1[i] != str2[j],那就说明子串不再连续了,所以不用像子序列那样分两种情况。同时,回溯构造子串也比较简单,因为子串都是连续的,只要记录下最长公共子串的最后一个字符的位置以及其长度,就能够直接得到该子串。

下面就是具体算法实现,时间复杂度O(mn)

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
import sys


def find_longest_common_substring(str1, str2):

c = [[0 for i in range(len(str2) + 1)] for j in range(len(str1) + 1)]

max_l = 0 # 记录最长的子串的长度
p = 0 # 记录最长子串对应在 str1 中的最后一位
for i in range(len(str1)):
for j in range(len(str2)):
if str1[i] == str2[j]:
c[i + 1][j + 1] = c[i][j] + 1
if c[i + 1][j + 1] > max_l:
max_l = c[i + 1][j + 1]
p = i

return str1[p + 1 - max_l:p + 1] # 切片出最长子串


if __name__ == '__main__':

input_strs = sys.stdin.readline().strip().split()

str1 = input_strs[0]
str2 = input_strs[1]

longest = find_longest_common_substring(str1, str2)

print longest, len(longest)