算法大挑战（KMP算法）

一、前记（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字符串查找方法