char st = "bacbababadababacambabacaddababacasdsd"; char pt = "ababaca"; KMP算法的核心，是一个被称为部分匹配表(Partial Match Table)的数组,"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度； 用到的公式：[P向右移动位数 = 已匹配的字符数 - 对应的部分匹配值（pmt_value）] -- 原模式串子串对应的各个前缀后缀的公共元素的最大长度表为《最大长度表》,next 数组相当于“最大长度值” 整体向右移动一位，然后初始值赋为-1。意识到了这一点，你会惊呼原来next 数组的求解竟然如此简单：就是找出对称长度的前缀后缀，然后整体右移一位，初值赋为-1（当然，你也可以直接计算某个字符…

KMP

def kmp(st,pt):
    # 传入一个母串和一个子串
    
    if len(pt)==0:
        return 0
    if len(st)==0:
        return -1
    
    # 生成next数组    
    next=[-1]*len(pt)
    if len(pt)>1:
    
        next[1]=0
        n,lens=1,0 #lens最大长度
        while n<len(pt)-1:
            if lens ==-1 or pt[n]==pt[lens]:
                n+=1
                lens+=1
                next[n]=lens
            else:
                lens=next[lens]
    #KMP 
    i,j=0,0
    while i<len(st) and j<len(pt):
    
        if j==-1 or st[i]==pt[j]:
            i+=1
            j+=1
        else:
            j=next[j]
    
    if j==len(pt):
        return i-j
    else:
        return -1

    

sunday

class Solution:    
    def sunday(self,text,patt):
        lent=len(text)
        lenp=len(patt)
        i=0
        j=0
        k=lenp
        while(k<lent):
            while (j<lenp and text[i]==patt[j]):
                i+=1
                j+=1
            if j==lenp:
                    return i-lenp#i，j重新匹配，成果则输出
            elif text[k] in patt:#匹配不成果跳到k，k在pattern里
                j=lenp-1
                while j>=0:
                    if text[k]==patt[j]:#从pattern末端开始向前对齐
                        for x in range(lenp):#如果能对齐，则逐个匹配
                            if text[k-j+x]!=patt[x]:
                                j-=1
                                break
                            elif text[k-j+lenp-1]==patt[lenp-1]:#匹配成果则输出
                                return k-j
                    else:
                        j-=1
                k+=lenp
                i+=lenp
                j=0
            else:#k不在pattern里
                
                k+=lenp+1
                i+=lenp+1
                j=0
        return -1
                
    def main(self):
        a='azcdfgsdbbobo'  
        b='bob'
        res=self.sunday(a,b)
        if res==-1:
            print 'no'
        else:
            print res
s=Solution()
s.main()