-
Notifications
You must be signed in to change notification settings - Fork 1
/
strStr.go
109 lines (102 loc) · 2.11 KB
/
strStr.go
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
package strstr
// func strStr(haystack string, needle string) int {
// for i, v := range haystack {
// right := i + len(needle)
// if right <= len(haystack) && string(needle[0]) == string(v) && needle == string(haystack[i:right]) {
// return i
// }
// }
// return -1
// }
// 方法一:前缀表使用减1实现
// getNext 构造前缀表next
// params:
//
// next 前缀表数组
// s 模式串
func getNext(next []int, s string) {
j := -1 // j表示 最长相等前后缀长度
next[0] = j
for i := 1; i < len(s); i++ {
for j >= 0 && s[i] != s[j+1] {
j = next[j] // 回退前一位
}
if s[i] == s[j+1] {
j++
}
next[i] = j // next[i]是i(包括i)之前的最长相等前后缀长度
}
}
func strStr(haystack string, needle string) int {
if len(needle) == 0 {
return 0
}
next := make([]int, len(needle))
getNext(next, needle)
j := -1 // 模式串的起始位置 next为-1 因此也为-1
for i := 0; i < len(haystack); i++ {
for j >= 0 && haystack[i] != needle[j+1] {
j = next[j] // 寻找下一个匹配点
}
if haystack[i] == needle[j+1] {
j++
}
if j == len(needle)-1 { // j指向了模式串的末尾
return i - len(needle) + 1
}
}
return -1
}
// 方法二: 前缀表无减一或者右移
// getNext 构造前缀表next
// params:
//
// next 前缀表数组
// s 模式串
func getNext1(next []int, s string) {
j := 0
next[0] = j
for i := 1; i < len(s); i++ {
for j > 0 && s[i] != s[j] {
j = next[j-1]
}
if s[i] == s[j] {
j++
}
next[i] = j
}
}
func strStr1(haystack string, needle string) int {
n := len(needle)
if n == 0 {
return 0
}
j := 0
next := make([]int, n)
getNext1(next, needle)
for i := 0; i < len(haystack); i++ {
for j > 0 && haystack[i] != needle[j] {
j = next[j-1] // 回退到j的前一位
}
if haystack[i] == needle[j] {
j++
}
if j == n {
return i - n + 1
}
}
return -1
}
func strStr2024(haystack string, needle string) int {
n, m := len(haystack), len(needle)
outer:
for i := 0; i+m <= n; i++ {
for j := range needle {
if haystack[i+j] != needle[j] {
continue outer
}
}
return i
}
return -1
}