0028. 找出字符串中第一个匹配项的下标 #
- 标签:字符串、双指针
- 难度:简单
题目大意 #
描述:给定两个字符串 haystack
和 needle
。
要求:在 haystack
字符串中找出 needle
字符串出现的第一个位置(从 0
开始)。如果不存在,则返回 -1
。
说明:
- 当
needle
为空字符串时,返回0
。 - $1 \le haystack.length, needle.length \le 10^4$。
haystack
和needle
仅由小写英文字符组成。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
字符串匹配的经典题目。常见的字符串匹配算法有: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 算法具体步骤如下:
- 对于给定的文本串
T
与模式串p
,求出文本串T
的长度为n
,模式串p
的长度为m
。 - 同时遍历文本串
T
和模式串p
,先将T[0]
与p[0]
进行比较。- 如果相等,则继续比较
T[1]
和p[1]
。以此类推,一直到模式串p
的末尾p[m - 1]
为止。 - 如果不相等,则将文本串
T
移动到上次匹配开始位置的下一个字符位置,模式串p
则回退到开始位置,再依次进行比较。
- 如果相等,则继续比较
- 当遍历完文本串
T
或者模式串p
的时候停止搜索。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:平均时间复杂度为 $O(n + m)$,最坏时间复杂度为 $O(m \times n)$。其中文本串 $T$ 的长度为 $n$,模式串 $p$ 的长度为 $m$。
- 空间复杂度:$O(1)$。
思路 2:RK(Robin Karp)算法 #
RK 算法思想:对于给定文本串 T
与模式串 p
,通过滚动哈希算快速筛选出与模式串 p
不匹配的文本位置,然后在其余位置继续检查匹配项。
RK 算法具体步骤如下:
- 对于给定的文本串
T
与模式串p
,求出文本串T
的长度为n
,模式串p
的长度为m
。 - 通过滚动哈希算法求出模式串
p
的哈希值hash_p
。 - 再通过滚动哈希算法对文本串
T
中n - m + 1
个子串分别求哈希值hash_t
。 - 然后逐个与模式串的哈希值比较大小。
- 如果当前子串的哈希值
hash_t
与模式串的哈希值hash_p
不同,则说明两者不匹配,则继续向后匹配。 - 如果当前子串的哈希值
hash_t
与模式串的哈希值hash_p
相等,则验证当前子串和模式串的每个字符是否真的相等(避免哈希冲突)。- 如果当前子串和模式串的每个字符相等,则说明当前子串和模式串匹配。
- 如果当前子串和模式串的每个字符不相等,则说明两者不匹配,继续向后匹配。
- 如果当前子串的哈希值
- 比较到末尾,如果仍未成功匹配,则说明文本串
T
中不包含模式串p
,方法返回-1
。
思路 2:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。其中文本串 $T$ 的长度为 $n$,模式串 $p$ 的长度为 $m$。
- 空间复杂度:$O(m)$。
思路 3:KMP(Knuth Morris Pratt)算法 #
KMP 算法思想:对于给定文本串 T
与模式串 p
,当发现文本串 T
的某个字符与模式串 p
不匹配的时候,可以利用匹配失败后的信息,尽量减少模式串与文本串的匹配次数,避免文本串位置的回退,以达到快速匹配的目的。
KMP 算法具体步骤如下:
- 根据
next
数组的构造步骤生成「前缀表」next
。 - 使用两个指针
i
、j
,其中i
指向文本串中当前匹配的位置,j
指向模式串中当前匹配的位置。初始时,i = 0
,j = 0
。 - 循环判断模式串前缀是否匹配成功,如果模式串前缀匹配不成功,将模式串进行回退,即
j = next[j - 1]
,直到j == 0
时或前缀匹配成功时停止回退。 - 如果当前模式串前缀匹配成功,则令模式串向右移动
1
位,即j += 1
。 - 如果当前模式串 完全 匹配成功,则返回模式串
p
在文本串T
中的开始位置,即i - j + 1
。 - 如果还未完全匹配成功,则令文本串向右移动
1
位,即i += 1
,然后继续匹配。 - 如果直到文本串遍历完也未完全匹配成功,则说明匹配失败,返回
-1
。
思路 3:代码 #
|
|
思路 3:复杂度分析 #
- 时间复杂度:$O(n + m)$,其中文本串 $T$ 的长度为 $n$,模式串 $p$ 的长度为 $m$。
- 空间复杂度:$O(m)$。
思路 4:BM(Boyer Moore)算法 #
BM 算法思想:对于给定文本串 T
与模式串 p
,先对模式串 p
进行预处理。然后在匹配的过程中,当发现文本串 T
的某个字符与模式串 p
不匹配的时候,根据启发策略,能够直接尽可能地跳过一些无法匹配的情况,将模式串多向后滑动几位。
BM 算法具体步骤如下:
- 计算出文本串
T
的长度为n
,模式串p
的长度为m
。 - 先对模式串
p
进行预处理,生成坏字符位置表bc_table
和好后缀规则后移位数表gs_talbe
。 - 将模式串
p
的头部与文本串T
对齐,将i
指向文本串开始位置,即i = 0
。j
指向模式串末尾位置,即j = m - 1
,然后从模式串末尾位置开始进行逐位比较。- 如果文本串对应位置
T[i + j]
上的字符与p[j]
相同,则继续比较前一位字符。- 如果模式串全部匹配完毕,则返回模式串
p
在文本串中的开始位置i
。
- 如果模式串全部匹配完毕,则返回模式串
- 如果文本串对应位置
T[i + j]
上的字符与p[j]
不相同,则:- 根据坏字符位置表计算出在「坏字符规则」下的移动距离
bad_move
。 - 根据好后缀规则后移位数表计算出在「好后缀规则」下的移动距离
good_mode
。 - 取两种移动距离的最大值,然后对模式串进行移动,即
i += max(bad_move, good_move)
。
- 根据坏字符位置表计算出在「坏字符规则」下的移动距离
- 如果文本串对应位置
- 如果移动到末尾也没有找到匹配情况,则返回
-1
。
思路 4:代码 #
|
|
思路 4:复杂度分析 #
- 时间复杂度:$O(n + \sigma)$,其中文本串 $T$ 的长度为 $n$,字符集的大小是 $\sigma$。
- 空间复杂度:$O(m)$。其中模式串 $p$ 的长度为 $m$。
思路 5:Horspool 算法 #
Horspool 算法思想:对于给定文本串 T
与模式串 p
,先对模式串 p
进行预处理。然后在匹配的过程中,当发现文本串 T
的某个字符与模式串 p
不匹配的时候,根据启发策略,能够尽可能的跳过一些无法匹配的情况,将模式串多向后滑动几位。
Horspool 算法具体步骤如下:
- 计算出文本串
T
的长度为n
,模式串p
的长度为m
。 - 先对模式串
p
进行预处理,生成后移位数表bc_table
。 - 将模式串
p
的头部与文本串T
对齐,将i
指向文本串开始位置,即i = 0
。j
指向模式串末尾位置,即j = m - 1
,然后从模式串末尾位置开始比较。- 如果文本串对应位置的字符
T[i + j]
与模式串对应字符p[j]
相同,则继续比较前一位字符。- 如果模式串全部匹配完毕,则返回模式串
p
在文本串中的开始位置i
。
- 如果模式串全部匹配完毕,则返回模式串
- 如果文本串对应位置的字符
T[i + j]
与模式串对应字符p[j]
不同,则:- 根据后移位数表
bc_table
和模式串末尾位置对应的文本串上的字符T[i + m - 1]
,计算出可移动距离bc_table[T[i + m - 1]]
,然后将模式串进行后移。
- 根据后移位数表
- 如果文本串对应位置的字符
- 如果移动到末尾也没有找到匹配情况,则返回
-1
。
思路 5:代码 #
|
|
思路 5:复杂度分析 #
- 时间复杂度:$O(n)$。其中文本串 $T$ 的长度为 $n$。
- 空间复杂度:$O(m)$。其中模式串 $p$ 的长度为 $m$。
思路 6:Sunday 算法 #
Sunday 算法思想:对于给定文本串 T
与模式串 p
,先对模式串 p
进行预处理。然后在匹配的过程中,当发现文本串 T
的某个字符与模式串 p
不匹配的时候,根据启发策略,能够尽可能的跳过一些无法匹配的情况,将模式串多向后滑动几位。
Sunday 算法具体步骤如下:
- 计算出文本串
T
的长度为n
,模式串p
的长度为m
。 - 先对模式串
p
进行预处理,生成后移位数表bc_table
。 - 将模式串
p
的头部与文本串T
对齐,将i
指向文本串开始位置,即i = 0
。j
指向模式串末尾位置,即j = m - 1
,然后从模式串末尾位置开始比较。- 如果文本串对应位置的字符
T[i + j]
与模式串对应字符p[j]
相同,则继续比较前一位字符。- 如果模式串全部匹配完毕,则返回模式串
p
在文本串中的开始位置i
。
- 如果模式串全部匹配完毕,则返回模式串
- 如果文本串对应位置的字符
T[i + j]
与模式串对应字符p[j]
不同,则:- 根据后移位数表
bc_table
和模式串末尾位置对应的文本串上的字符T[i + m - 1]
,计算出可移动距离bc_table[T[i + m - 1]]
,然后将模式串进行后移。
- 根据后移位数表
- 如果文本串对应位置的字符
- 如果移动到末尾也没有找到匹配情况,则返回
-1
。
思路 6:代码 #
|
|
思路 6:复杂度分析 #
- 时间复杂度:$O(n)$。其中文本串 $T$ 的长度为 $n$。
- 空间复杂度:$O(m)$。其中模式串 $p$ 的长度为 $m$。