kmt字符串匹配

# -*- coding:utf-8 -*-

class StringPattern:
    def findAppearance(self, A, lena, B, lenb):
        pos=0
        tmp = 0
        pmtlist= self.pmt(B)
        mp=[]
        while pos<len(A):
            if  B[tmp]==A[pos] :
                if tmp==len(B)-1:
                   return pos-tmp
                else:
                    tmp=tmp+1
                    pos=pos+1
            else:
                if tmp!=0:
                    pos=pos-pmtlist[tmp-1]
                    tmp=0
                else:
                    pos=pos+1
        return -1
        # write code here
    def pmt(self,initialstr=''):
        pmtlist=[]
        for i in range(len(initialstr)):
            prefix=[]
            suffix=[]
            matchcount=0
            substr=initialstr[0:i+1]
            for j in range(len(substr)):
                prefix.append(substr[0:j-1])
                suffix.append(substr[i-j+1:i+1])
        #print(substr,prefix,suffix)
            for k in prefix:
                if k in suffix:
                    matchcount=len(k)
            pmtlist.append(matchcount)
        return pmtlist
a=StringPattern()
print(a.findAppearance('abcbabcabfg',11,'abcab',5))

欢迎批评指正！
巴特西

kmt字符串匹配

最新文章

热门文章
