Kmp算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Kmp算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1616字，纯文字阅读大概需要3分钟。

内容图文

一：Kmp算法

概要：

Kmp算法中nxt数组为重要组成部分,nxt数组所存的内容为：next[i]表示前i个字符组成的子串的最长相同前缀和后缀的长度,要注意应用中提出的nxt[i]变化（方便在匹配两个字符串时候跳动减少时间复杂度)

nxt数组模板：

以i=1为起点的字符串进行处理

void get_nxt()
{
    nxt[0]=nxt[1]=0;
    for(int i=2,j=0;i<=m;++i){
        while(j&&b[j+1]!=b[i]) j=nxt[j];//交换后从头再次匹配前缀和后缀
        if(b[j+1]==b[i])
            ++j;
        nxt[i]=j;
    }
}

应用：

 

　　　　求前缀串子串的周期和子串的长度

　　　　求前缀串在原串中能匹配的次数

 

1.POJ-1961  Period

题意：

　　求字符串的每个前缀串是否有周期,和周期的具体值

 

　　若此字符串前缀和后缀相同的情况则会发生nxt[i]连续加的情况 

　　所以求前缀传是否为周期串是会出现叠加的情况,根据叠加情况此时的i-nxt[i]即为所求串的长度,若%为0则满足条件,只需要仔细想想就会发现满足%为0的就是所求的len！因为nex[i]是在前缀后缀相同的情况下会叠加

 

2.HDU-3336 Count the string
题意：
　　求一个串的前缀在这个串中有多少个匹配
　　此题网上很多人的解法都是错误的会有aaa答案是5的情况但其实aaa的答案是6
　　aaa-a*3-aa*2-aaa
　　dp[i]=dp[nxt[i]]+1的理解
　　dp[i]代表的是以第i个字符结尾的前缀串所具有的匹配个数,这个个数就是他所匹配的前缀中有的+上他自己的一个就是他的
　　比如说dp[8]=dp[3]+1,那么这个以8结尾的前缀串中含有一个长度为3的前缀后缀相同,则他这个后缀匹配个数为前缀所能匹配的相同+1,微小状态的叠加

int main()
{
    int t;scanf("%d",&t);
    while(t--){
        scanf("%d%s",&m,b+1);
        get_nxt();
        dp[0]=0;//相当于初始化了数组
        int ans=0;
        for(int i=1;i<=m;++i){
            dp[i]=dp[nxt[i]]+1;//dp
            dp[i]%=mod;
            ans=(ans+dp[i])%mod;
        }
        printf("%d\n",ans);

    }
}

 

 

 最后放两个学习Kmp时候看的博客

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

https://www.cnblogs.com/SYCstudio/p/7194315.html

 

 

 

内容总结

以上是互联网集市为您收集整理的Kmp算法全部内容，希望文章能够帮你解决Kmp算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---