0028. 实现 strStr()

0028. 实现 strStr() #

  • 标签:字符串、双指针
  • 难度:简单

题目大意 #

描述:给定两个字符串 haystackneedle

要求:在 haystack 字符串中找出 needle 字符串出现的第一个位置(从 0 开始)。如果不存在,则返回 -1

说明

  • needle 为空字符串时,返回 0
  • $1 \le haystack.length, needle.length \le 10^4$。
  • haystackneedle 仅由小写英文字符组成。

示例

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)
本站总访问量  次  |  您是本站第  位访问者