代码随想录算法训练营|day9

28.实现strStr()

(1)KMP算法：视频讲解 题目详解
前缀：所有以第一个字符开头的连续子串，不包含最后一个字符。
后缀：所有以最后一个字符结尾的连续子串，不包含第一个字符。
next数组存储了模式串最长相等前后缀，j指向前缀末尾，i指向后缀末尾

寻找与不匹配位置之前字符串最长相等前后缀长度的位置，跳转并进行后续匹配

func strStr(haystack string, needle string) int {
    n := len(needle)
    if n == 0 {
        return 0
    }
    j := 0 
    next := make([]int, n)
    getNext(next, needle)
    for i := 0; i < len(haystack); i++{
        // 若模式串与文本串不匹配，j跳转前缀表中前一位的位置。最不济j跳转到0[边界]，重新匹配
        //j跳转前缀表中前一位的位置
        for j > 0 && haystack[i] != needle[j] {
            j = next[j - 1]
        }
        if haystack[i] == needle[j] {
            j++
        }
        if j == n {
            return i - n + 1
        }
    }
    return -1
}

func getNext(next[] int, s string){
    j := 0
    next[j] = 0
    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
    }
}
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

(2)暴力求解
外循环控制匹配起点，若匹配返回index，否则向右移动

func strStr(haystack string, needle string) int {
    m, n := len(haystack), len(needle)
    for i := 0; i + n <= m; i++ {
        flag := true
        for j := 0; j < n; j++ {
            if haystack[i + j] != needle[j] {
                flag = false
                break
            }
        }
        if flag {
            return i
        }
    }
    return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(3)内置库函数

func strStr(haystack string, needle string) int {
    index := strings.Index(haystack, needle)
	return index
}
1
2
3
4

459.重复的子字符串
文章详解

func repeatedSubstringPattern(s string) bool {
    j, n := 0, len(s)
    next := make([]int, n)
    next[j] = 0
    for i := 1; i < n; i++{
        for j > 0 && s[i] != s[j] {
            j = next[j - 1]
        }
        if s[i] == s[j] {
            j++
        }
        next[i] = j
    }
    if next[n - 1] != 0 && n % (n - next[n - 1]) == 0 {
        return true
    }
    return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

字符串总结

双指针回顾

总结

感谢卡哥大佬的视频和图解，效率提升不少。KMP算法还得再学习理解。
next数组记录了模式串子串中最长相等前后缀长度，减少了与文本串不匹配时的循环次数。