一、前记(2/3)
浑浑噩噩,感觉每天的时间都不够用,到了12点总结的时候,发现还有一些题没做,还有一些东西没背(太烦!!)。数学题每天花上2,3个小时只能写上40道题左右,这在考研考试的时候怎么够用呢?单词背了就忘,好像每天都在和遗忘打仗。今天尝试着听了一下徐涛老师的考研政治,全程就是:我是谁?我在哪里?我在干嘛?如果到了后面还是这样不太好的复习状态,那可能会暂停一下“算法大挑战”这个系列。
二、题目描述

在这道题里面要注意几个点:1、haystack里面的有完整的needle字符串,而不是零散的字符。2、空字符串返回的结果是0。3、不存在相匹配的字符串返回的结果为-1.
三、解题思路
1、我的思路
其实我的思路比较简单:首先只能循环查找len(haystack)-len(needle)次,因为我们需要找到的是“在haystack里面完整的needle字符串”。并且如果我们找到haystack里面有一个字符与needle的第一个字符相同。那么我们可以看是否haystack[i+len(needle)]==needle。如果相等就返回i,不相等的话继续寻找,最终完成循环。
#encoding:utf-8
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
i=0
if len(needle)==0: #如果为空字符串
return 0
n=len(needle)
for i in range(len(haystack)-n+1):
if haystack[i:i+n]==needle: #是否相等
return i
else:
i+=1
if i>(len(haystack)-n): #完成循环
return -1
#as a checking
solution=Solution()
a="aaaaa"
b="bba"
print(solution.strStr(a,b))
2、别人的思路(KMP算法)
在学习别人的思路的时候,我看到一个非常有意思的名称叫做“KMP算法”,相当于是一种字符串查找方法。我这里不再详述,俺觉得阮一峰就讲的很清楚。
参考代码:
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if needle == "":
return 0
# generate pnext
i, k, m = 0, -1, len(needle)
pnext = [-1] * m
while i < m - 1:
if k == -1 or needle[i] == needle[k]:
i, k = i + 1, k + 1
if needle[i] == needle[k]:
pnext[i] = pnext[k]
else:
pnext[i] = k
else:
k = pnext[k]
# matching
h, j = 0, 0
n = len(haystack)
while h < m and j < n:
if h == -1 or needle[h] == haystack[j]:
h, j = h + 1, j + 1
else:
h = pnext[h]
if h == m:
return j - h
return -1
四、学到了什么?
1、一个非常棒的KMP字符串查找方法