当前位置 博文首页 > 明圣的博客：leetcode每日一题——28. 实现 strStr()（简单篇）
字符串匹配问题：一般两种方法：暴力匹配法和kmp算法
方法一：暴力解法
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
haystack_length = len(haystack)
needle_length = len(needle)
i = 0
while i+needle_length <= haystack_length:
flag = True
for j in range(0,needle_length):
if haystack[i+j] != needle[j]:
flag = False
break
if flag:
return i
i += 1
return -1
#改编自官方的java代码
超出时间限制，可能因为最后这个实例太长了。
方法二：kmp算法
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
a=len(needle)
b=len(haystack)
if a==0:
return 0
next=self.getnext(a,needle)
p=-1
for j in range(b):
while p>=0 and needle[p+1]!=haystack[j]:
p=next[p]
if needle[p+1]==haystack[j]:
p+=1
if p==a-1:
return j-a+1
return -1
def getnext(self,a,needle):
next=['' for i in range(a)]
k=-1
next[0]=k
for i in range(1,len(needle)):
while (k>-1 and needle[k+1]!=needle[i]):
k=next[k]
if needle[k+1]==needle[i]:
k+=1
next[i]=k
return next
#此代码引用于「代码随想录」
这么经典的kmp算法还真是烧脑，于是我决定单独写一篇kmp算法的总结
cs