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:记得之后总结。
标签:第九天,return,前缀,needle,随想录,len,next,字符串 From: https://www.cnblogs.com/wuyijia/p/17411109.html