[代码随想录]Day08-字符串 part02
题目: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
}
参考:
代码随想录
总结:
周六周天补KMP