28. Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

KMP算法,很久没写了,这个题目正好复习一下

KMP算法挺复杂的,不容易理解,这里是它的思路:http://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.html

下面是我实现的代码:

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if needle =='':
            return 0
        if haystack =='' and needle!='':
            return -1
        next = self.makeNext(needle)
        i =0
        j =0
        while i <len(haystack):
            if j==-1 or haystack[i] == needle[j]:
                i+=1
                j+=1
            else :
                j = next[j]
            if j ==len(needle):
                return i -j
        return -1

    def makeNext(self,p):
        next = [0 for i in range(len(p)+1)]
        next[0]=-1
        k =-1
        j = 0
        while j<len(p)-1:
            if k==-1 or p[j]==p[k]:
                k+=1
                j+=1
                next[j]= k
            else :
                k = next[k]
        return next