题目大意
#
描述：给定两个字符串 haystack 和 needle。
要求：在 haystack 字符串中找出 needle 字符串出现的第一个位置（从 0 开始）。如果不存在，则返回 -1。
说明：
- 当
needle 为空字符串时，返回 0。
- $1 \le haystack.length, needle.length \le 10^4$。
haystack 和 needle 仅由小写英文字符组成。
示例：
1
2
|
输入：haystack = "hello", needle = "ll"
输出：2
|
解题思路
#
字符串匹配的经典题目。常见的字符串匹配算法有：BF（Brute Force）算法、RK（Robin-Karp）算法、KMP（Knuth Morris Pratt）算法、BM（Boyer Moore）算法、Horspool 算法、Sunday 算法等。
思路 1：BF（Brute Force）算法代码
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
i = 0
j = 0
len1 = len(haystack)
len2 = len(needle)
while i < len1 and j < len2:
if haystack[i] == needle[j]:
i += 1
j += 1
else:
i = i - (j - 1)
j = 0
if j == len2:
return i - j
else:
return -1
|
思路 2：RK（Robin-Karp）算法代码
#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
def rabinKarp(T: str, p: str) -> int:
len1, len2 = len(T), len(p)
hash_p = hash(p)
for i in range(len1 - len2 + 1):
hash_T = hash(T[i: i + len2])
if hash_p != hash_T:
continue
k = 0
for j in range(len2):
if T[i + j] != p[j]:
break
k += 1
if k == len2:
return i
return -1
return rabinKarp(haystack, needle)
|
思路 3：KMP（Knuth Morris Pratt）算法代码
#
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
|
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
# KMP 匹配算法，T 为文本串，p 为模式串
def kmp(T: str, p: str) -> int:
n, m = len(T), len(p)
next = generateNext(p) # 生成 next 数组
i, j = 0, 0
while i < n and j < m:
if j == -1 or T[i] == p[j]:
i += 1
j += 1
else:
j = next[j]
if j == m:
return i - j
return -1
# 生成 next 数组
# next[i] 表示坏字符在模式串中最后一次出现的位置
def generateNext(p: str):
m = len(p)
next = [-1 for _ in range(m)] # 初始化数组元素全部为 -1
i, k = 0, -1
while i < m - 1: # 生成下一个 next 元素
if k == -1 or p[i] == p[k]:
i += 1
k += 1
if p[i] == p[k]:
next[i] = next[k] # 设置 next 元素
else:
next[i] = k # 退到更短相同前缀
else:
k = next[k]
return next
return kmp(haystack, needle)
|
思路 4：BM（Boyer Moore）算法代码
#
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
|
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
def boyerMoore(T: str, p: str) -> int:
n, m = len(T), len(p)
bc_table = generateBadCharTable(p) # 生成坏字符位置表
gs_list = generageGoodSuffixList(p) # 生成好后缀规则后移位数表
i = 0
while i <= n - m:
j = m - 1
while j > -1 and T[i + j] == p[j]:
j -= 1
if j < 0:
return i
bad_move = j - bc_table.get(T[i + j], -1)
good_move = gs_list[j]
i += max(bad_move, good_move)
return -1
# 生成坏字符位置表
def generateBadCharTable(p: str):
bc_table = dict()
for i in range(len(p)):
bc_table[p[i]] = i # 坏字符在模式串中最后一次出现的位置
return bc_table
# 生成好后缀规则后移位数表
def generageGoodSuffixList(p: str):
m = len(p)
gs_list = [m for _ in range(m)]
suffix = generageSuffixArray(p)
j = 0
for i in range(m - 1, -1, -1):
if suffix[i] == i + 1:
while j < m - 1 - i:
if gs_list[j] == m:
gs_list[j] = m - 1 - i
j += 1
for i in range(m - 1):
gs_list[m - 1 - suffix[i]] = m - 1 - i
return gs_list
def generageSuffixArray(p: str):
m = len(p)
suffix = [m for _ in range(m)]
for i in range(m - 2, -1, -1):
start = i
while start >= 0 and p[start] == p[m - 1 - i + start]:
start -= 1
suffix[i] = i - start
return suffix
return boyerMoore(haystack, needle)
|
思路 5：Horspool 算法代码
#
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
|
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
def horspool(T: str, p: str) -> int:
n, m = len(T), len(p)
bc_table = generateBadCharTable(p)
i = 0
while i <= n - m:
j = m - 1
while j > -1 and T[i + j] == p[j]:
j -= 1
if j < 0:
return i
i += bc_table.get(T[i + m - 1], m)
return -1
# 生成后移位置表
# bc_table[bad_char] 表示坏字符在模式串中最后一次出现的位置
def generateBadCharTable(p: str):
m = len(p)
bc_table = dict()
for i in range(m - 1):
bc_table[p[i]] = m - i - 1 # 更新坏字符在模式串中最后一次出现的位置
return bc_table
return horspool(haystack, needle)
|
思路 6：Sunday 算法代码
#
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
|
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
# sunday 算法，T 为文本串，p 为模式串
def sunday(T: str, p: str) -> int:
n, m = len(T), len(p)
if m == 0:
return 0
bc_table = generateBadCharTable(p) # 生成后移位数表
i = 0
while i <= n - m:
if T[i: i + m] == p:
return i # 匹配完成，返回模式串 p 在文本串 T 中的位置
if i + m >= n:
return -1
i += bc_table.get(T[i + m], m + 1) # 通过后移位数表，向右进行进行快速移动
return -1 # 匹配失败
# 生成后移位数表
# bc_table[bad_char] 表示遇到坏字符可以向右移动的距离
def generateBadCharTable(p: str):
m = len(p)
bc_table = dict()
for i in range(m):
bc_table[p[i]] = m - i # 更新遇到坏字符可向右移动的距离
return bc_table
return sunday(haystack, needle)
|