简介

z-box算法可用于普通KMP、扩展KMP，国外非常流行但是国内却几乎没有人用，这种算法在解决许多字符串问题时都比KMP要直观许多。

算法详解

对于一个字符串s,设它的长度为len

z[i]所表示的是s[i…len-1]与s[0…len-1]的最长公共前缀

如何求出z[i]数组？

递推即可

对于一个新的i,我们把i前面的所有z[j]看成一个区间[j,z[j]],记录右端点最大的区间[l,r],如果i>r,那么我们暴力和s[1..len]进行匹配，代码如下（注意下标从0开始）:

if (i>r)
{
    int t=i,bg=0;
    while (b[t]==b[bg])
        t++,bg++;
    z[i]=bg;
    r=t-1;
    l=i;
}

如果 i<=r i <= r ，说明i一定被右端点最大区间[l,r]所覆盖，说明[l,r]和[0,r-l]是相同的，那么在[l,r]内，z[i]和z[i-l]也是相同的，类似manacher的思想，我们需要分类讨论一下：如果 z[i−l]<r−i+1 z [ i − l ] < r − i + 1 ,即在i-l匹配到的区间长度小于r-i+1的话，那么我们直接赋值即可，如果不是，我们需要对r后进行暴力匹配，代码如下:

if (i<=r)
{
    if (z[i-l]<r-i+1) z[i]=z[i-l];
    else
    {
        int t=r+1,bg=r-i+1;
        while (b[t]==b[bg])
            t++,bg++;
        z[i]=bg;
        r=t-1;
        l=i;
    }
}

算法用途

字符串匹配

给出字符串n,m,求m在n中出现的次数以及出现位置

令s=m+’$’+n（这里的’\$’是指一个分隔符，不在题目所给出的字符集之内即可）

对s求出他的z数组，假设m的长度为lenm，n的长度为lenn，那么我们只需在z[lenm+1…lenm+lenn]里面找出值为lenm的位置即可。