Z algorithm

Z函数也叫扩展KMP算法，因为思路和KMP很像，都是从已经获得的信息中处理后面的信息。

思路参考：

灵茶山艾府-Z函数 （听了这个才听懂）

OI WIKI

算法demo程序

模板：

#include<vector>
#include<cstring>
#include<iostrea>
using namespace std;

vector<int> (string s)
{
    int len = s.size();

    vector<int> z(n);

    for (int i = 1, l = 0, r = 0; i < n;i ++)
    {
        if(i <= r && z[i - 1] < r - i + 1)//首先处理可以直接等的情况
        {
            z[i] = z[i - l];
        }else
        {
            z[i] = max(0, r - i + 1); //r - i + 1 等于i - 1时，在z-box里面的把从i到r占满了，所以要往后暴力枚举
            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; //当匹配的新串的长度比z-box的范围要大就更新z-box
    }
    return z;//返回z
}