代码随想录算法训练营第九天|28. 找出字符串中第一个匹配项的下标、459. 重复的子字符串

【参考链接】

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

【注意】

1.kmp解决的就是字符串匹配的问题。

2.kmp如何知道匹配过哪些字符串，并跳到匹配过的内容后面的字符。---前缀表

3.找到一个子字符串里它的最长相等前后缀。

4.前缀是包含首字母，不包含尾字母的所有子串；后缀只包含尾字母，不包含首字母的所有子串。

5.eg.aabaaf:前缀表是010120----next数组（遇见冲突，向前回退找的方式不一样）。

6.n为文本串长度，m为模式串长度，时间复杂度是O(n+m)的。

【代码】

实现步骤：

1.初始化。

2.前后缀不相同。

3.前后缀相同。

4.next

i后缀末尾，j前缀末尾。 i包括i之前这个子串的最长相等先后缀。

next[j]就是记录着j（包括j）之前的子串的相同前后缀的长度。

 1 class Solution(object):
 2     def strStr(self, haystack, needle):
 3         """
 4         :type haystack: str
 5         :type needle: str
 6         :rtype: int
 7         """
 8         #前缀表不减一
 9         if len(needle) == 0:
10             return 0
11         
12         next = self.getNext(needle) #前缀表
13         j = 0
14 
15         for i in range(len(haystack)):
16             while j>0 and haystack[i] != needle[j]:
17                 j = next[j-1]
18             if haystack[i] == needle[j]:
19                 j += 1
20             if j == len(needle): #匹配成功，返回第一个匹配项的下标
21                 return i - len(needle) + 1 # 2-3+1=0  haystack = "sadbutsad", needle = "sad" 返回0
22         
23         return -1
24 
25     
26     def getNext(self, needle):
27         next = [0] * len(needle)
28         j = 0
29         next[0] = j
30 
31         for i in range(1,len(needle)):
32             while j > 0 and needle[i] != needle[j]:
33                 #不相等
34                 j = next[j-1] #回退
35             if needle[i] == needle[j]:
36                 #相等
37                 j += 1 #后缀首字母的前一位
38             next[i] = j
39 
40         return next

459. 重复的子字符串

【代码】

 1 class Solution(object):
 2     def repeatedSubstringPattern(self, s):
 3         """
 4         :type s: str
 5         :rtype: bool
 6         """
 7         #前缀表（不减一）的代码实现
 8         if len(s) == 0:
 9             return False
10         
11         next = [0] * len(s)
12         self.getNext(next, s)
13 
14         if next[-1] != 0 and len(s) %(len(s)-next[-1]) == 0:  #有前缀表
15             return True
16 
17         return False
18 
19     def getNext(self, next, s):
20         next[0] = 0
21         j = 0
22         for i in range(1, len(s)):
23             while j>0 and s[i] != s[j]:
24                 j = next[j-1]
25             if s[i] == s[j]:
26                 j += 1
27             next[i] = j
28 
29         return next

ps：记得之后总结。