28. 实现 strStr()
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
示例 1：
1
2
| 输入：haystack = "hello", needle = "ll"
输出：2
|
示例 2：
1
2
| 输入：haystack = "aaaaa", needle = "bba"
输出：-1
|
KMP
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
| // strStr KMP算法 时间复杂度O(N+M),空间复杂度O(M)
func strStrSimple(haystack string, needle string) int {
n, m := len(haystack), len(needle)
if m == 0 {
return 0
}
next := make([]int, m)
GetNext(next, needle)
// 因为next数组里记录的起始位置为0
j := 0
// i从0开始匹配
for i := 0; i < n; i++ {
// 如果不匹配，就寻找之前匹配的位置
for j > 0 && haystack[i] != needle[j] {
j = next[j-1]
}
// 如果匹配，i和j同时向后移动
if haystack[i] == needle[j] {
j++
}
// 如果j从0移动到m的位置，意味着模式串needle与文本串haystack匹配成功
if j == m {
return i - m + 1
}
}
return -1
}
func GetNext(next []int, s string) {
// next[j]就是记录着j（包括j）之前的子串的相同前后缀的长度。
j := 0
next[0] = 0
// j指向前缀起始位置，i指向后缀起始位置
for i := 1; i < len(s); i++ {
// 如果前后缀不相同，那么j就要向前回退
for j > 0 && s[i] != s[j] {
j = next[j-1]
}
// 说明找到了相同的前后缀, j++，同时记录next[i]
if s[i] == s[j] {
j++
}
next[i] = j
}
}
|