《扩展 KMP（Z 函数）》重写版

· · 题解

前言

这篇文章是对《扩展 KMP（Z 函数）》的批判性重写，时隔近两年再看《扩展 KMP（Z 函数）》，我自己都看不懂了，所以这篇文章力求让大家能够以一种简洁明了的方式理解 扩展 KMP。

希望这篇题解能对你有帮助 ヾ(◍ ╹ ∇ ╹ ◍)ﾉﾞ！

分析

国外一般将计算该数组的算法称为 Z Algorithm，而国内则称其为 扩展 KMP。

扩展 KMP 这个名称很好的揭露这个算法的本质：像 KMP，却又不是 KMP。 KMP 的本质是对一个字符串的前缀内部比较前缀与后缀，而扩展 KMP 的本质是将一个字符串与它自身的后缀比较前缀。所以我们要做的就是从两者的相同出发，而将两者的不同区分开。

z 数组

首先，我们要知道 z 数组的定义，即 s[0,z_i-1]=s[i,i+z_i-1] 时 z_i 取极大值。根据此定义可得 z_0=|s|。

参照 KMP 的 next 数组，本算法应该也是由前往后逐渐递推往后，所以求 z_i 时，我们应尽可能地用到前面的 z_j(0<j<i)。

假设我们现在已经推到了 i，由图可知，s[0,z_{i-k}-1]=s[i,i+z_{i-k}-1]，也就是说 z_i\ge z_{i-k}；而又因为 s[z[i-k]]\ne s[i-k+z[i-k]]=s[i+z[i-k]]，所以 z_i=z_{i-k}。

那么这个问题是否就解决了呢？再来考虑这么一种边界情况：

这时，原来推论的条件不再满足，为了解决这个问题，我们应该将 z_{i-k} 与 (k+z_k-1)-i+1=k+z_k-i 取最小值。这时又有了一个问题：我们需要额外加入特殊操作保证 (k+z_k-1)-i+1=k+z_k-i 最大以减少暴力增加次数保证时间复杂度吗？

答案是不用。因为 s[k+z_k]\ne s[z_k]=s[k-i+z_k]，也就是说 z_i 不可能更大了。

这种情况同理，因为 z_k 没有向后延申，说明下一位肯定是不等的。

两种情况下所需的暴力跳次数和 k 都没有关系，所以我们应该可以任意取一个 k。

另一串字符串

稍加调整即可。

代码

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#define debug 0
std::vector<int>extend_KMP1(std::string s)
{
    std::vector<int>z(s.size());
    z[0]=s.size();
    int max_z_down=0;//z 数组最大值的下标
    z[1]=0;
    for(int i=1,k;i<s.size();i++)
    {
        if(i!=1)
        {
            k=i-max_z_down;
            z[i]=std::min(z[max_z_down],std::max(0,/*k+z[k]-i*/z[k]-max_z_down));
        }
        while((i+z[i]-1)+1<s.size()&&s[(z[i]-1)+1]==s[(i+z[i]-1)+1])++z[i];
        if(z[i]>z[max_z_down])max_z_down=i;
    }
    return z;
}
std::vector<int>extend_KMP2(std::string s,std::string q,std::vector<int>z)
{
    std::vector<int>p(q.size());
    int max_z_down=0;//z 数组最大值的下标
    for(int i=0,k;i<q.size();i++)
    {
        if(i!=0)
        {
            k=i-max_z_down;
            p[i]=std::min(z[max_z_down],std::max(0,/*k+p[k]-i*/p[k]-max_z_down));
        }
        while(p[i]<s.size()&&i+p[i]<q.size()&&s[p[i]]==q[i+p[i]])++p[i];
        if(i<z.size()&&z[i]>z[max_z_down])max_z_down=i;
    }
    return p;
}
using namespace std;
int main()
{
    long long ans_z=0,ans_p=0;
    string a,b;
    cin>>a>>b;
    std::vector<int>z=extend_KMP1(b);
    #if debug
    for(int i=0;i<z.size();i++){cout<<z[i]<<' ';}
    #endif
    for(int i=0;i<z.size();i++){ans_z^=(i+1)*(long long)(z[i]+1);}
    cout<<ans_z<<endl;
    std::vector<int>p=extend_KMP2(b,a,z);
    #if debug
    for(int i=0;i<p.size();i++){cout<<p[i]<<' ';}
    #endif
    for(int i=0;i<p.size();i++){ans_p^=(i+1)*(long long)(p[i]+1);}
    cout<<ans_p<<endl;
    return 0;
}

如果这么交上去，你就会发现，你 T 飞了。

再分析

以上，就是我一开始做这道题的心路历程。T 飞是因为我们忽略了一种情况：i 要是没有在 k 的覆盖下怎么办？

这个时候，请什么过来都没用了，只能暴力算。因此，我们应尽量减少这种情况的发生。那怎么减少呢？

两种情况下所需的暴力跳次数和 k 都没有关系，所以我们应该可以任意取一个 k。

这个时候就是 k 派上用场的时候，只要让 k+z_k-1 尽可能地大，就可以减少这种情况的发生。

感觉很眼熟？没错，其实这个 k 和 k+z_k-1 就是其他题解中的 l 和 r，只不过本文以一种循序渐进的方式将其引出。

代码

此处应有剪贴板代码

此处应有评测记录链接

感谢

加油吧！✧*٩( ◕ᗜ ◕ )و✧*

  • 超多颜文字的可爱文章
  • Z 函数（扩展 KMP）- OI Wiki
  • 全 luogu 最强的巨犇