kmp算法

# coding=utf-8
# This is a sample Python script.
# Press Shift+F10 to execute it or replace it with your code.
# Press Double Shift to search everywhere for classes, files, tool windows, actions, and settings.
# Definition for singly-linked list.
#kmp算法
class Solution(object):
    def strStr(self, haystack, needle):
        '''
        :param target_str:
        :param pattern_str:
        :return:
        '''
        def ListCmp(i, m):#常规比较串相等返回T否则，返回F
            j = 0
            while i <= m:
                if needle[j] == needle[i]:
                    i += 1
                    j += 1
                else:
                    return False
            return True
        list_pattern = [0]  # 此表用来记录模式串每个长度的最长子串
        def ListPattern():
            for a in range(1, len(needle)):  # 感觉是个递归啊？m去查m-1的表，如果
                for guard_bh in range((a - list_pattern[a - 1]), a + 1):
                    if ListCmp(guard_bh, a) == True:  # 匹配上了加入list_pattern，如果到最后还没匹配到
                        list_pattern.append(a - guard_bh + 1)
                        break
                    else:
                        if guard_bh == a:
                            list_pattern.append(0)
                        else:
                            pass
        if needle=='':
            return ''
        else:
            ListPattern()
            i=0
            j=0
            while i!=len(haystack) or((len(haystack)-i)>(len(needle)-j)):
                if haystack[i]==needle[j]:#相等
                    if j==len(needle)-1:#如果已经是最后一个字符
                        return i-j
                    else:#如果不是，继续匹配
                        i+=1
                        j+=1
                else:#如果不相等，将i，j索引赋给模式串匹配函数
                    if j==0:
                        i+=1
                    else:
                        j=list_pattern[j-1]
            return -1

对应leetcode28题，看了kmp的原理自己写的实现，先用表将模式串的每个索引的最长公共前后缀写一张表，然后每次出现匹配不到的情况都去表中取相应的公共前后缀长度，来调整模式串指针的位置