求一个字符串的z函数

定义

约定：字符串下标以 0为起点。
对于一个长度为 n的字符串s ,定义函数$z[i]$ 表示 s和 $s[i,n-1]$（即以 s[i]开头的后缀）的最长公共前缀的长度。 z被称为 s的 Z 函数。特别地，z[0]=0
$z[0]$置为$len$也行，不影响计算

朴素算法 $O(n^2)$

双重循环暴力计算

vector<int> get_z(strinhg s)
{
    int len=s.size();
    vector<int> z(len);
    z[0]=0;
    for(int i=1;i<len;i++)
    {
        while(i+z[i]<len&&s[i+z[i]]==s[z[i]]) z[i]++;
    }
    return z;
}

优化算法$O(n)$

利用前面的匹配信息计算当前的z值

算法思路

• 维护一个r值最大的$s[l,r]$使得$s[l,r]==s[0,r-l]$
• 计算$z[i]$
  • 如果i>r，没有信息可以利用，只能暴力枚举，并更新r值
  • 如果i<=r
    • 因为$s[l,r]==s[0,r-l]$ 且 $i<=r$
    • 所以 $s[i,r]==s[i-l,r-l]$
    • 如果 $z[i-l]<r-i+1$的话，那么$z[i]=z[i-l]$
    • 反之，$z[i]>=r-i+1$ 可以从这里开始往后暴力枚举，得到$z[i]$，并更新$l,r$
• 结束
• 初始化 $l=r=0$

vector<int> get_z1(string s)
{
    int len=s.size();
    vector<int> z(len);
    z[0]=0;
    int l=0,r=0;
    for(int i=1;i<len;i++)
    {
        if(i>r)
        {
            //暴力枚举
            while(i+z[i]<len&&s[i+z[i]]==s[z[i]]) z[i]++;
            //更新l，r
            if(i+z[i]-1>r)
            {
                l=i;
                r=i+z[i]-1;
            }
        }
        else
        {
            if(z[i-l]<r-i+1)
            {
                z[i]=z[i-l];
            }
            else
            {
                z[i]=r-i+1;
                //暴力枚举
                while(i+z[i]<len&&s[i+z[i]]==s[z[i]]) z[i]++;
                //更新l，r
                if(i+z[i]-1>r)
                {
                    l=i;
                    r=i+z[i]-1;
                }
            }
        }
    }
    return z;
}