实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2
示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1
说明: 当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。 对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
思路:KMP算法
KMP的经典思想就是: 当出现字符串不匹配时,可以记录一部分之前已经匹配的文本内容,利用这些信息避免从头再去做匹配。
next数组:前缀表:记录下标i之前(包括i)的字符串中,有多大长度的相同前缀后缀。
前缀表是用来回退的,它记录了当模式串与主串不匹配的时候,模式串应该从哪里和主串重新匹配。
前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
举个例子:
比如:
模式串:aabaabaaf
字符串:aabaaf
前面匹配了aabaab和aabaaf,发现最后一位不匹配,这个时候,我们知道,前一位也就是aabaa的最后一个a,它对应数字2,就是说最后两个单位长度的后缀,是和它的前缀一样的。所以我们只需要从aabaa的倒数第二个元素对应的原字符串的位置重新开始找。
相当于是,我们发现f这个位置不匹配了,但我们之前f前面的aa,和子串的前两位aa,是一样的,所以子串从它后两位aa对应的长串的位置,重新看aa后面的b与长串aa的后面是不是对应就可以了。
时间复杂度分析:
其中n为文本串长度,m为模式串长度,因为在匹配的过程中,根据前缀表不断调整匹配的位置,可以看出匹配的过程是O(n),之前还要单独生成next数组,时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。
暴力的解法显而易见是O(n × m),所以KMP在字符串匹配中极大地提高了搜索的效率。
生成next数组的过程讲解:
class Solution:def getNext(self, next, s):j=-1next[0] = jfor i in range(1, len(s)):while j>=0 and s[i] != s[j+1]:j=next[j]if s[i] == s[j+1]:j += 1next[i] = jdef strStr(self, haystack: str, needle: str) -> int:if not needle:return 0next = [0] * len(needle)self.getNext(next, needle)j = -1for i in range(len(haystack)):while j >= 0 and haystack[i] != needle[j+1]:j = next[j]if haystack[i] == needle[j+1]:j += 1if j == len(needle) - 1:return i-len(needle)+1return -1
这道题还挺难的。以后还需要时常复习和思考。
5月13日 重写:
class Solution:def getNext(self, next, s):j=-1next[0]=jfor i in range(1,len(s)):while j>=0 and s[i]!=s[j+1]:j=next[j]if s[i]==s[j+1]:j+=1next[j] = jdef strStr(self, haystack: str, needle: str) -> int:j=-1next=[0]*len(needle)nd = self.getNext(next,needle)for i in range(1,len(nd)):while j>=0 and haystack[i]!=needle[j+1]:j=nd[j]if haystack[i]==needle[j+1]:j+=1
错误点:
在得到next数组的时候,是next[i]=j,而不是next[j]=j
j只是一个暂时的变量,如果不相等,j就回退,如果相等,j就加1,并且让next[i]=j
在寻找needle的时候:
先检查needle是不是为空,如果是,就返回0(在haystack的开头就是空)
不需要让nd=self.getNext(next, needle),因为getNext这个函数传入了next这个list,并且改变了这个list,使得里面有数值,不需要再让另一个list等于它了。
在得到next数组的时候,i从1开始,因为next[0]已经等于j。
但是,在遍历haystack的时候,i从0开始。
判断最后是否在haystack中找到了needle:if j==len(needle)-1
【其实这个点我想到了,但是不知道对不对,所以没有写。看来以后要自信大胆写。】
(因为这个next数组是-1版本的,所以判断条件是j==len(needle)-1)
i指向的是haystack对应的,needle末尾的位置,所以return i-len(needle)+1, 就是needle头出现在haystack的位置了。
如果直到i遍历完,都没有进入这个if,那么就跳出for loop, return -1
注意:
第二个function中,是for i in range(len(haystack)), 而不是for i in range(len(needle))
里面的判断,if statement, 是 haystack[i]和needle[j+1]比较, 而不是haystack[i]和needle[j+1]比较。注意!