0028. 找出字符串中第一个匹配项的下标

0028. 找出字符串中第一个匹配项的下标 #

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

题目大意 #

描述:给定两个字符串 haystackneedle

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

说明

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

示例

1
2
3
4
5
6
7
输入haystack = "hello", needle = "ll"
输出2
解释"sad" 在下标 06 处匹配第一个匹配项的下标是 0 所以返回 0 

输入haystack = "leetcode", needle = "leeto"
输出-1
解释"leeto" 没有在 "leetcode" 中出现所以返回 -1 

解题思路 #

字符串匹配的经典题目。常见的字符串匹配算法有:BF(Brute Force)算法、RK(Robin-Karp)算法、KMP(Knuth Morris Pratt)算法、BM(Boyer Moore)算法、Horspool 算法、Sunday 算法等。

思路 1:BF(Brute Force)算法 #

BF 算法思想:对于给定文本串 T 与模式串 p,从文本串的第一个字符开始与模式串 p 的第一个字符进行比较,如果相等,则继续逐个比较后续字符,否则从文本串 T 的第二个字符起重新和模式串 p 进行比较。依次类推,直到模式串 p 中每个字符依次与文本串 T 的一个连续子串相等,则模式匹配成功。否则模式匹配失败。

BF 算法具体步骤如下:

  1. 对于给定的文本串 T 与模式串 p,求出文本串 T 的长度为 n,模式串 p 的长度为 m
  2. 同时遍历文本串 T 和模式串 p,先将 T[0]p[0] 进行比较。
    1. 如果相等,则继续比较 T[1]p[1]。以此类推,一直到模式串 p 的末尾 p[m - 1] 为止。
    2. 如果不相等,则将文本串 T 移动到上次匹配开始位置的下一个字符位置,模式串 p 则回退到开始位置,再依次进行比较。
  3. 当遍历完文本串 T 或者模式串 p 的时候停止搜索。

思路 1:代码 #

 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

思路 1:复杂度分析 #

  • 时间复杂度:平均时间复杂度为 $O(n + m)$,最坏时间复杂度为 $O(m \times n)$。其中文本串 $T$ 的长度为 $n$,模式串 $p$ 的长度为 $m$。
  • 空间复杂度:$O(1)$。

思路 2:RK(Robin Karp)算法 #

RK 算法思想:对于给定文本串 T 与模式串 p,通过滚动哈希算快速筛选出与模式串 p 不匹配的文本位置,然后在其余位置继续检查匹配项。

RK 算法具体步骤如下:

  1. 对于给定的文本串 T 与模式串 p,求出文本串 T 的长度为 n,模式串 p 的长度为 m
  2. 通过滚动哈希算法求出模式串 p 的哈希值 hash_p
  3. 再通过滚动哈希算法对文本串 Tn - m + 1 个子串分别求哈希值 hash_t
  4. 然后逐个与模式串的哈希值比较大小。
    1. 如果当前子串的哈希值 hash_t 与模式串的哈希值 hash_p 不同,则说明两者不匹配,则继续向后匹配。
    2. 如果当前子串的哈希值 hash_t 与模式串的哈希值 hash_p 相等,则验证当前子串和模式串的每个字符是否真的相等(避免哈希冲突)。
      1. 如果当前子串和模式串的每个字符相等,则说明当前子串和模式串匹配。
      2. 如果当前子串和模式串的每个字符不相等,则说明两者不匹配,继续向后匹配。
  5. 比较到末尾,如果仍未成功匹配,则说明文本串 T 中不包含模式串 p,方法返回 -1

思路 2:代码 #

 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)

思路 1:复杂度分析 #

  • 时间复杂度:$O(n)$。其中文本串 $T$ 的长度为 $n$,模式串 $p$ 的长度为 $m$。
  • 空间复杂度:$O(m)$。

思路 3:KMP(Knuth Morris Pratt)算法 #

KMP 算法思想:对于给定文本串 T 与模式串 p,当发现文本串 T 的某个字符与模式串 p 不匹配的时候,可以利用匹配失败后的信息,尽量减少模式串与文本串的匹配次数,避免文本串位置的回退,以达到快速匹配的目的。

KMP 算法具体步骤如下:

  1. 根据 next 数组的构造步骤生成「前缀表」next
  2. 使用两个指针 ij,其中 i 指向文本串中当前匹配的位置,j 指向模式串中当前匹配的位置。初始时,i = 0j = 0
  3. 循环判断模式串前缀是否匹配成功,如果模式串前缀匹配不成功,将模式串进行回退,即 j = next[j - 1],直到 j == 0 时或前缀匹配成功时停止回退。
  4. 如果当前模式串前缀匹配成功,则令模式串向右移动 1 位,即 j += 1
  5. 如果当前模式串 完全 匹配成功,则返回模式串 p 在文本串 T 中的开始位置,即 i - j + 1
  6. 如果还未完全匹配成功,则令文本串向右移动 1 位,即 i += 1,然后继续匹配。
  7. 如果直到文本串遍历完也未完全匹配成功,则说明匹配失败,返回 -1

思路 3:代码 #

 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)

思路 3:复杂度分析 #

  • 时间复杂度:$O(n + m)$,其中文本串 $T$ 的长度为 $n$,模式串 $p$ 的长度为 $m$。
  • 空间复杂度:$O(m)$。

思路 4:BM(Boyer Moore)算法 #

BM 算法思想:对于给定文本串 T 与模式串 p,先对模式串 p 进行预处理。然后在匹配的过程中,当发现文本串 T 的某个字符与模式串 p 不匹配的时候,根据启发策略,能够直接尽可能地跳过一些无法匹配的情况,将模式串多向后滑动几位。

BM 算法具体步骤如下:

  1. 计算出文本串 T 的长度为 n,模式串 p 的长度为 m
  2. 先对模式串 p 进行预处理,生成坏字符位置表 bc_table 和好后缀规则后移位数表 gs_talbe
  3. 将模式串 p 的头部与文本串 T 对齐,将 i 指向文本串开始位置,即 i = 0j 指向模式串末尾位置,即 j = m - 1,然后从模式串末尾位置开始进行逐位比较。
    1. 如果文本串对应位置 T[i + j] 上的字符与 p[j] 相同,则继续比较前一位字符。
      1. 如果模式串全部匹配完毕,则返回模式串 p 在文本串中的开始位置 i
    2. 如果文本串对应位置 T[i + j] 上的字符与 p[j] 不相同,则:
      1. 根据坏字符位置表计算出在「坏字符规则」下的移动距离 bad_move
      2. 根据好后缀规则后移位数表计算出在「好后缀规则」下的移动距离 good_mode
      3. 取两种移动距离的最大值,然后对模式串进行移动,即 i += max(bad_move, good_move)
  4. 如果移动到末尾也没有找到匹配情况,则返回 -1

思路 4:代码 #

 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)

思路 4:复杂度分析 #

  • 时间复杂度:$O(n + \sigma)$,其中文本串 $T$ 的长度为 $n$,字符集的大小是 $\sigma$。
  • 空间复杂度:$O(m)$。其中模式串 $p$ 的长度为 $m$。

思路 5:Horspool 算法 #

Horspool 算法思想:对于给定文本串 T 与模式串 p,先对模式串 p 进行预处理。然后在匹配的过程中,当发现文本串 T 的某个字符与模式串 p 不匹配的时候,根据启发策略,能够尽可能的跳过一些无法匹配的情况,将模式串多向后滑动几位。

Horspool 算法具体步骤如下:

  1. 计算出文本串 T 的长度为 n,模式串 p 的长度为 m
  2. 先对模式串 p 进行预处理,生成后移位数表 bc_table
  3. 将模式串 p 的头部与文本串 T 对齐,将 i 指向文本串开始位置,即 i = 0j 指向模式串末尾位置,即 j = m - 1,然后从模式串末尾位置开始比较。
    1. 如果文本串对应位置的字符 T[i + j] 与模式串对应字符 p[j] 相同,则继续比较前一位字符。
      1. 如果模式串全部匹配完毕,则返回模式串 p 在文本串中的开始位置 i
    2. 如果文本串对应位置的字符 T[i + j] 与模式串对应字符 p[j] 不同,则:
      1. 根据后移位数表 bc_table 和模式串末尾位置对应的文本串上的字符 T[i + m - 1] ,计算出可移动距离 bc_table[T[i + m - 1]],然后将模式串进行后移。
  4. 如果移动到末尾也没有找到匹配情况,则返回 -1

思路 5:代码 #

 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)

思路 5:复杂度分析 #

  • 时间复杂度:$O(n)$。其中文本串 $T$ 的长度为 $n$。
  • 空间复杂度:$O(m)$。其中模式串 $p$ 的长度为 $m$。

思路 6:Sunday 算法 #

Sunday 算法思想:对于给定文本串 T 与模式串 p,先对模式串 p 进行预处理。然后在匹配的过程中,当发现文本串 T 的某个字符与模式串 p 不匹配的时候,根据启发策略,能够尽可能的跳过一些无法匹配的情况,将模式串多向后滑动几位。

Sunday 算法具体步骤如下:

  1. 计算出文本串 T 的长度为 n,模式串 p 的长度为 m
  2. 先对模式串 p 进行预处理,生成后移位数表 bc_table
  3. 将模式串 p 的头部与文本串 T 对齐,将 i 指向文本串开始位置,即 i = 0j 指向模式串末尾位置,即 j = m - 1,然后从模式串末尾位置开始比较。
    1. 如果文本串对应位置的字符 T[i + j] 与模式串对应字符 p[j] 相同,则继续比较前一位字符。
      1. 如果模式串全部匹配完毕,则返回模式串 p 在文本串中的开始位置 i
    2. 如果文本串对应位置的字符 T[i + j] 与模式串对应字符 p[j] 不同,则:
      1. 根据后移位数表 bc_table 和模式串末尾位置对应的文本串上的字符 T[i + m - 1] ,计算出可移动距离 bc_table[T[i + m - 1]],然后将模式串进行后移。
  4. 如果移动到末尾也没有找到匹配情况,则返回 -1

思路 6:代码 #

 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)

思路 6:复杂度分析 #

  • 时间复杂度:$O(n)$。其中文本串 $T$ 的长度为 $n$。
  • 空间复杂度:$O(m)$。其中模式串 $p$ 的长度为 $m$。
本站总访问量  次  |  您是本站第  位访问者