字符串 （3）--- KMP 算法的扩展

对于个长度为n的字符串s。定义函数z[i]表示s和s[i,n-1]（即以 s[i] 开头的后缀）的最长公共前缀（LCP）的长度。z被称为s的Z函数。特别地，z[0] = 0。

如同大多数字符串主题所介绍的算法，其关键在于，运用自动机的思想寻找限制条件下的状态转移函数，使得可以借助之前的状态来加速计算新的状态。

在该算法中，我们从1到n-1顺次计算z[i]的值（z[0]=0）。
在计算z[i]的过程中，我们会利用已经计算好的z[0],...,z[i-1]。
对于i，我们称区间[i, i+z[i]-1]是i的匹配段，也可以叫Z-box。
算法的过程中我们维护右端点最靠右的匹配段。为了方便，记作 [l, r]。
根据定义，s[l, r] 是s的前缀。在计算 z[i] 时我们保证l <= i。初始时l=r=0。
计算完前i-1个z函数，维护Z-box的[l, r], 则s[l, r] = s[0, r-l]。
在计算z[i]的过程中：
（1）如果 i <= r（在Z-box内），那么根据 [l, r] 的定义有 s[i, r] = s[i-l, r-l] 同时减l，
    因此 z[i] >= min(z[i-l], r-i+1)。
    这时：
        若 z[i-l] < r-i+1，则 z[i] = z[i-l]。
        否则 z[i-l] >= r-i+1，这时我们令 z[i] = r-i+1，
        然后暴力枚举下一个字符扩展 z[i] 直到不能扩展为止。
（2）如果 i > r（在Z-box外），那么我们直接按照朴素算法，从s[i]开始比较，暴力求出z[i]。
在求出z[i]后，如果i+z[i]-1 > r，我们就需要更新[l,r]，即令 l=i, r=i+z[i]-1。

当i=4时,l=4,r=5, 我们发现s[4~5]==s[0~1],z[4]==z[0],z[5]==z[1]
即如果存在s[i~r]==s[i-l~r-l], 可以直接更新z[i]=z[i-l]。
否则，逐位比较去得出i位置的z函数值

#include
#include
using namespace std;

vector z_fun(string& s) 
{
    int n = (int) s.length();
    vector z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i)
    {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]); // r-i+1: 右端点r到i的距离
        // 逐位比较，字符串下标从0开始，双指针分别指向z[i]和i+z[i]
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
        {
            l = i;
            r = i + z[i] - 1;
        }
    }

    return z;
}

int main()
{
    string s = "aaabaab";
    vector vec = z_fun(s);

    return 0;
}

对KMP与扩展KMP的对比：
（1）应用场景：KMP用于计算两个字符串的最大公共前后缀，而扩展KMP则是计算一个字符串与另一个字符串（或是本身）后缀子串的最长公共前缀。

（2）算法实现：KMP借助next数组的预处理实现指针滞留；扩展KMP借助z函数数组的预处理和Z-box实现新状态的加速更新。

（3）时间复杂度：都是从暴力实现的o(n^2)优化至了o(n)。