[代码随想录]Day08-字符串 part02

WtcSky / 2023-08-04 / 原文

题目：28. 找出字符串中第一个匹配项的下标

思路：

说白了就是匹配字符串，朴素就是暴力以每一个位置为起点都跑一遍。

这个题的核心是学会KMP算法，为啥这题是个简单难度...KMP周六周日补上

代码1：

朴素的暴力

func strStr(haystack string, needle string) int {
    for i := 0 ; i <= len(haystack) - len(needle); i++ { // 如果小于len(needle)剪枝
        f := 1
        t := i
        for j := 0; j < len(needle); j++ { // 从每个节点开始逐个比对
            if haystack[t] != needle[j] { // 如果有不一样的就退出 f标记为0
                f = 0
                break
            }
            t++
        }
        if f == 1 { // 如果f没有被修改说明匹配完成
            return i // 返回当前的头部坐标
        }
    }
    return -1
}

参考：

代码随想录

题目：459. 重复的子字符串

思路：

朴素的做法把所有可能的长度都遍历一遍

进阶KMP，没想好

代码：

func repeatedSubstringPattern(s string) bool {
    lens := len(s)
    for i:=1;  i * 2 <= lens; i++ { // 遍历子串长度
        if lens % i == 0 { // 剪枝，字符串长度不是子串长度的倍数不可能拼出来
            match := 1
            for j := i; j < lens; j++ { // 遍历一遍字符串
                if s[j] != s[j-i] { // 确保在i个位置之前元素相同
                    match = 0
                    break
                }
            }
            if match == 1 {
                return true
            }
        }
    }
    return false
}