温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Python如何实现KPM算法

发布时间:2021-12-08 11:06:20 来源:亿速云 阅读:116 作者:小新 栏目:开发技术

这篇文章主要介绍Python如何实现KPM算法,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!

知识点说明:

先说前缀,和后缀吧

比如有一个串:abab

则在下标为3处的(前缀和后缀都要比下标出的长度小1,此处下标为3出的长度是4)

前缀为:a,ab,aba

后缀为:b,ba,bab

一、要获取KPM算法的next[]数组

简单说一下原理吧,首先k,用来存放前缀的下标,首先初始化j=0(j用来表示模式串的下标,一直去模式串的每一位与前面的进行比较,如果相等,则记录下当前位置与前面的哪个位置相同,我们这里主要是要记录相同位置的下一个位置,就是不相同的位置,从不相同的位置开始比较,就是回溯到不相同位置,所以这里在t[j]==t[k]成立的时候要j+1,为了比较下一个位置是否相同,k也要+1),模式串从0开始,k=-1,next[0]=-1第一个位置赋默认值-1;

此处串采用=“abab”

第一次循环:

判断k是否等于-1,如果等于则,j和k都+1,

此时j=1,k=0,next[1]=0,也就是第2个位置(下标1)的回溯位置还是0,因为前缀的最大长度必须小于当前位置的长度;

第二次循环:

j=1,k=0,next[1]=0;k已经不等于-1了,判断t[j]==t[k],t[1]==t[0],t[1]="b",t[0]="a",不相等

执行else:

k=next[0]=-1

第三次循环:

k==-1

j和k都+1,j=2,k=0,next[2]=0

第四次循环:

k不等于-1,判断t[2]==t[0],t[2]=“a”=t[0]=“a”,成立

j和k都+1,j=3,k=1,next[3]=1

此时next=[-1,0,0,1],next[3]=1表示在next[3]处发生不匹配时,也就是模式串下标为3时为“b”,说明前面aba都是和目标串都匹配,所以模式串不匹配位置前面的串aba一定与目标串不匹配位置前面的前3个值相等,也就是aba,所以此刻,只需要回溯到模式串的1位置,也就是模式串的b,模式串b前面是a,满足目标串的前一个a。

第五次循环:

k依旧是不等于-1,就是比较上一个位置后面的两个数再进行比较,简单的说,以此取出每一项与第一项比较,如果存在相等的就再比较下一个与第二项是否相等。

代码如下:

def GetNext(t, next):
    j, k = 0, -1
    next[0] = -1
    while j < len(t) - 1:
        if k == -1 or t[j] == t[k]:  # 如果k==-1 或者 开始位置和结尾位置有相同的元素
            j, k = j + 1, k + 1  # j和k都加1,当前位匹配,则从下一个位置开始匹配,所以k+1;j再进行取下一位判断是否也是匹配,所以也要+1
            next[j] = k  # 当前位置要取k项
        else:#如果不相等,再把k置-1,下一次循环再进行+1操作,j这个位置再存入0,表示无匹配项
            k = next[k]
    return next

二、KMP函数

原理和BF算法是一样的,唯独不同的是,当模式串与目标串不匹配的时候,不直接回溯模式串,而是根据模式串的next[]表,查询要回溯到的位置,直接回溯到模式串的指定位置,KMP算法的核心也就在这里,但是这种方法一般只对前缀和后缀存在相同元素时,有效果,也就是说相同部分是一样的就不再进行比较了,从相同元素的下一个位置开始比较,所以KMP算法最复杂的部分其实就是找next[]表,要找出模式串的每一个位置,是否有相同前缀,如果有则标注该相同位置,下次回溯就不用回溯到0这个位置,可以从不相同位置开始。

def KMP(s, t):
    next = [0] * len(t)
    next = GetNext(t, next)
    print(next)
    i, j = 0, 0
    while i < len(s) and j < len(t):
        if j == -1 or s[i] == t[j]:
            i, j = i + 1, j + 1
        else:
            j = next[j]
    if j >= len(t):
        return i - len(t)
    else:
        return -1

完整代码:

def GetNext(t, next):
    j, k = 0, -1
    next[0] = -1
    while j < len(t) - 1:
        if k == -1 or t[j] == t[k]:  # 如果k==-1 或者 开始位置和结尾位置有相同的元素
            j, k = j + 1, k + 1  # j和k都加1,当前位匹配,则从下一个位置开始匹配,所以k+1;j再进行取下一位判断是否也是匹配,所以也要+1
            next[j] = k  # 当前位置要取k项
        else:#如果不相等,再把k置-1,下一次循环再进行+1操作,j这个位置再存入0,表示无匹配项
            k = next[k]
    return next
 
 
def KMP(s, t):
    next = [0] * len(t)
    next = GetNext(t, next)
    print(next)
    i, j = 0, 0
    while i < len(s) and j < len(t):
        if j == -1 or s[i] == t[j]:
            i, j = i + 1, j + 1
        else:
            j = next[j]
    if j >= len(t):
        return i - len(t)
    else:
        return -1
 
 
if __name__ == '__main__':
    re = KMP('asdfghjsssaaasdfaaaabababcdabd', "ababaaaababaa")
    print(re)

结果:

Python如何实现KPM算法

以上是“Python如何实现KPM算法”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI