Python|实现KMP算法字符串匹配

a

b

a

b

c

a

b

c

a

c

b

a

b

a

b

c

a

c

a

b

c

a

c

a

b

c

a

c

a

b

c

a

c

a

b

c

a

c

Next

-1

0

0

0

1

a

b

a

b

c

a

b

c

a

c

b

a

b

a

b

c

a

c

a

b

c

a

c

a

b

c

a

c

class Text:

    def __init__(self):

        self.dic={}#定义一个字典，来存储并计算字符下标next

        self.next=[]#将得到的下标放入next中

    def A(self,s):# s为模式串

        for i in range(len(s)):

            if i not in self.dic:# 将每个模式串的字符下标储存在字典中，初始值为0

                self.dic[i] = 0 

            if i>=2:

                for j in range(1,i):# 循环

                    if s[:i][:j]==s[:i][-j:]: # 找到最长的相同前后缀

                        self.dic[i]=len(s[:i][:j]) # 记录相应点最长的相同前后缀

            if i==0: # 第一个点的下标一定为-1

                self.dic[i]=-1

        for ke in self.dic: #遍历字典将得到的下标放入next中

            self.next.append(self.dic[ke])

    def B(self,gl,s):# gl代表目标串，s代表模式串

        for i in range(len(gl)): #遍历gl的字符串下标值

            for j in range(len(s)): #遍历s的字符串下标值

                if len(gl[i:])<len(s): #当gl从i位置取到最后的长度小于s的长度，返回False匹配失败

                    return False

                if gl[i]!=s[0]: #如果目标串的值不等于模式串的第一个值，那么就进行下一个目标串的循环

                    break

                if j==len(s)-1 and gl[i+j]==s[j]:#当满足最后一个模式串与目标串对应位置相等时返回匹配成功

                    return True

                if gl[i+j]!=s[j]:#如果该位置不等

                    if self.B(gl[i+j:],s[self.next[j]:]):#递归判断，gl返回不相等的位置即gl[i+j],s则返回next所对应的下标s的位置。如果得到True，结束递归，反之得到False

                        return True

                    else:

                        return False

    def C(self,gl,s):

        if self.B(gl,s):

            print('True')

        else:

            print('False')

f=Text()

gl='ababcabcacbab'

s='abcac'

f.A(s)

f.C(gl,s)

#输出：

#True