KMP算法python实现

#File Name : KMP算法.py

def getIndexOf(str1,str2):
    #判断，str2是否在str1中
    def getNextArray(strS):
        #用于返回strS中 每个位置匹配度的数组
        if len(strS) == 1:
            return [-1]
        nextArr = [0 for i in range(len(strS))]
        nextArr[0] = -1
        nextArr[1] = 0
        pos = 2
        cn = 0
        while pos < len(strS):
            if strS[pos-1] == strS[cn]:
                nextArr[pos] = cn+1
                pos+=1
                cn+=1
            elif cn==0:
                nextArr[pos] = 0
                pos+=1
            else:
                cn = nextArr[cn]
        return nextArr

    if str1==None or str2==None or len(str2)<1 or len(str1)<len(str2):
        return -1
    nextArr = getNextArray(str2)
    i1 = 0
    i2 = 0
    while i1<len(str1) and i2<len(str2):
        if str1[i1]==str2[i2]:
            i1+=1
            i2+=1
        #说明 i2=0 此时连第一个都对不上
        elif nextArr[i2] == -1:
            i1+=1
        else:
            i2 = nextArr[i2]

    return -1 if i2 != len(str2) else i1-i2

a = 'efabcabcd'
b = 'abcabc'

print(getIndexOf(a,b))