关于KMP的两个版本

December 6, 2017 技术杂烩

KMP版本众多,不禁让初学者有些眼花缭乱。下面我收集了两种大众喜闻乐见的KMP算法版本:

入门经典版(推荐):

字符串从0开始,fail数组从0开始。

    //计算fail数组
    for (int i=1,j=0;b[i];i++)
    {
        while (j&&b[i]!=b[j])j=p[j];
        f[i+1]=(b[i]==b[j])?j++:0;
    }
    //匹配
    for (int i=1,j=0;a[i];i++)
    {
        while (j&&a[i]!=b[j])j=p[j];
        if (a[i]==b[j])j++;
            if (j==m)ans++;
    }

杨队长版:

字符串从1开始,fail数组从1开始。

    //计算fail数组
    for (int i=2,j=0;b[i];i++)
    {
        while (j&&b[i]!=b[j+1])j=p[j];
        p[i]=(j+=(b[i]==b[j+1]));
    }
    //匹配
    for (int i=1,j=0;a[i];i++)
    {
        while (j&&a[i]!=b[j+1])j=p[j];
        if ((j+=(b[j+1]==a[i]))==m)ans++;
    }

添加新评论