kmp算法学习 与 传参试验（常回来看看）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了kmp算法学习 与 传参试验（常回来看看），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3388字，纯文字阅读大概需要5分钟。

内容图文

　　之前在codeforces上做了一道类似KMP的题目，但由于之前没有好好掌握，现在又基本忘记，并没能解答。下面是对KMP算法的一点小总结。

　　首先KMP算法的核心是纸在匹配过程中，利用模式串的前后缀来加速匹配过程，这一点在自己实验时就可以发现了。其次时KMP算法的核心Next数组，next[j]=k表示对于模式串的【0...j-1】位，最长存在长度为k的相同前后缀，值得注意的是对于kmp而言是不能出现next[j]=j的情况的。而next数组的计算方法我认为本质上还是DP，但是在状态转移过程中又用到了递归的想法，因此使得算法变得复杂。

　　下面是codeforces上的next数组变种题：http://codeforces.com/contest/1200/problem/E

　　需要利用next数组的思想，将要合并的两个字符串构建成“S2+S1"的形式，其中的“+”可以防止匹配越界，还应该注意构建时取S1.S2的最小长度从而减小时间复杂度。最后利用next[]的最后一位即可得到合并部分的长度。

　　这里是自己比较习惯的利用for循环完成next数组构建的写法。

 #include <stdio.h>
 
char ch[1000010];
int next[1000010];
 
char* mmerge(char* ch1,char* ch2,int &len1,int len2)
{
   //printf("%d %d ",len1,len2);
    int len=len1;if (len2<len) len=len2;
 
    for (int i=0;i<len;i++)
        ch[i]=ch2[i];
    ch[len]='+';
    for (int i=len*2,j=len1-1;i>len;i--,j--)
        ch[i]=ch1[j];
    ch[len*2+1]=0;
   // printf("%s\n",ch);
 
    next[0]=0;
    for (int i=1;i<=len*2;i++)
    {
        int j=next[i-1];
        while (j && ch[i]!=ch[j])
            j=next[j-1];
        if ( ch[i]==ch[j] ) next[i]=j+1;
        else next[i]=0;
    }
 
    //printf(" %d ",next[len*2]);
    for(int i=next[len*2];ch2[i];i++,len1++ )
        ch1[len1]=ch2[i];
    ch1[len1]=0;
 
    //printf("%s\n\n",ch1);
    return ch1;
}
 
int main()
{
    char ch1[1000010];
    int n;scanf("%d",&n);
    scanf("%s",ch1);
    int len1=0;
    while (ch1[len1]) len1++;
    for(int i=1;i<n;i++)
    {
        char ch2[1000010];
        scanf("%s",ch2);
        int len2=0;while (ch2[len2]) len2++;
        mmerge(ch1,ch2,len1,len2);
    }
    printf("%s",ch1);
}

View Code

　　也有正常使用while循环的写法（可能不标准吧）

#include <stdio.h>

char ch[1000010];
int next[1000010];

char* mmerge(char* ch1,char* ch2,int &len1,int len2)
{
    
    int len=len1;if (len2<len) len=len2;

    for (int i=0;i<len;i++)
        ch[i]=ch2[i];
    ch[len]='+';
    for (int i=len*2,j=len1-1;i>len;i--,j--)
        ch[i]=ch1[j];
    ch[len*2+1]=0;


    next[0]=0;
    int now=1,mlen=0;
    while (now<=len*2)
    {
        if (ch[now]==ch[mlen])
        {
            next[now]=mlen+1;
            now++;mlen++;
        }
        else
        if (mlen==0)
            next[now++]=0;
        else
            mlen = next[mlen-1];
    }

    for(int i=next[len*2];ch2[i];i++,len1++ )
        ch1[len1]=ch2[i];
    ch1[len1]=0;

    return ch1;
}

int main()
{
    char ch1[1000010];
    int n;scanf("%d",&n);
    scanf("%s",ch1);
    int len1=0;
    while (ch1[len1]) len1++;
    for(int i=1;i<n;i++)
    {
        char ch2[1000010];
        scanf("%s",ch2);
        int len2=0;while (ch2[len2]) len2++;
        mmerge(ch1,ch2,len1,len2);
    }
    printf("%s",ch1);
}

View Code

　　在程序中，也大胆尝试了以前不敢用的传递对象指针以及利用引用&完成传值的操作，希望以后能多用一些这种编程方式，有利于工程实践。另外最开始将ch数组与next数组放置于mmerge函数中，似乎出现了栈溢出的问题（以后需要关注，还不太明白）。

　　接着做了一道正常KMP例题，http://acm.hdu.edu.cn/showproblem.php?pid=1686，问S1在S2串中出现了多少次？

#include <stdio.h>

int ans( char* S, char* P, int* next )
{
    int aans=0;
    int len1=0;while (S[len1]) len1++;
    int len2=0;while (P[len2]) len2++;
    next[0]=-1;
    int now=0,mlen=-1;
    while (now<len1)
    {
        if (mlen==-1 || S[now]==S[mlen] )
        {
            mlen++;
            now++;
            next[now]=mlen;
        }
        else
            mlen=next[mlen];
    }

    int i=0,j=0;
    while (j<len2)
    {
        if (i==len1) aans++,i=next[i];
        if (i==-1 || S[i]==P[j])
            i++,j++;
        else
            i=next[i];

    }
    if (i==len1) aans++;
    return aans;

}

int main()
{
    int T;scanf("%d",&T);
    while (T--)
    {
        char ch1[10010];
        char ch2[1000010];
        scanf("%s%s",ch1,ch2);
        int next[10010];
        printf("%d\n", ans(ch1,ch2,next) );
    }
}

View Code

　　对于KMP，目前理解了原理，自己也能写出代码，不过感觉还是不够熟练，时常回来看看吧：）

内容总结

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

内容备注

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

内容手机端

---