28.strStr()
https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/
实现strStr()代码随想录
https://programmercarl.com/0028.实现strStr.html#思路
459.重复字符串
https://leetcode.cn/problems/repeated-substring-pattern/submissions/538631105/
重复字符串代码随想录
https://programmercarl.com/0459.重复的子字符串.html#其他语言版本
实现strStr() —— 字符串匹配
题目
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
题解方法——KMP
举例：aabaaf
前缀：a;aa;aab;aaba;aabaa;
后缀: f;af;aaf;baaf;abaaf;
前缀表：求最长相等前后缀->遇见冲突位置向前回退
| 字符串 | 最长相等前后缀 |
|---|---|
| a | 0 |
| aa | 1 |
| aab | 0 |
| aaba | 1 |
| aabaa | 2 |
| aabaaf | 0 |
得到next表后，挨个匹配。j表示在模式中的遍历。如果字符串和模式不匹配，回退到上一个匹配点，继续匹配。
题解代码
class Solution:
def getnext(self,s):
next_ = [0]*len(s)
j = 0
for i in range(1,len(s)):
while j>0 and s[i]!=s[j]:
j = next_[j-1]
if s[i] == s[j]:
j = j+1
next_[i] = j
return next_
def strStr(self, haystack: str, needle: str) -> int:
if len(needle)==0:
return 0
next_ = self.getnext(needle)
j = 0
for i in range(len(haystack)):
while j>0 and haystack[i]!=needle[j]:
j = next_[j-1]
if haystack[i]==needle[j]:
j = j+1
if j==len(needle):
return i-len(needle)+1
return -1
459.重复字符串
题目
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成
题解
- 思路1：移动匹配：移动匹配法。如果内部是由重复字符串组成，那必然前后重组的新字符串中也包含原有的字符串；即s[1:]+s[:-1]中也含有s
- 思路2：找到最大相同前后缀，len(s)-最大相同前后缀的长度是否能整除;如果可以整除，则说明是重复模块；
## 思路1
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
if len(s)<=1:
return False
ss = s[1:]+s[:-1]
return ss.find(s)!=-1
## 思路2
class Solution:
def getnext(self,s):
next_ = [0]*len(s)
j = 0
for i in range(1,len(s)):
while j>0 and s[j]!=s[i]:
j = next_[j-1]
if s[j]==s[i]:
j = j+1
next_[i] = j
return next_
def repeatedSubstringPattern(self, s: str) -> bool:
if len(s)==0:
return True
next_ = self.getnext(s)
if next_[-1]!=0 and len(s)%(len(s)-next_[-1])==0:
return True
else:
return False