对于不知道什么是KMP算法的同学，请先学习KMP算法！

$零.$扩展KMP算法的用途

其实对考取省一没有任何用途（悲）

作为NOI级的知识，扩展KMP算法可以……

$壹.$Z函数的定义

(约定：字符串下标以 0 为起点。)

对于一个长度为 $n$ 的字符串 $s$，定义函数 $z[i]$ 表示 $s$ 和 $s[i,n-1]$（即以 $s[i]$ 开头的后缀）的最长公共前缀$（LCP）$的长度，则 $z$ 被称为 $s$ 的 $Z$ 函数。特别地，$z[0] = 0$。 国外一般将计算该数组的算法称为 Z Algorithm，而国内则称其为 扩展 KMP。

来自 OI Wiki 的介绍

概念显然是晦涩难懂的，我们举一个例子：

一个字符串$s=$abacaba,计算得出$z(abacaba)=$[0,0,1,0,3,0,1]。

要计算$z[n]$，就要先得到字符串s的从第n项开始的后缀，算出它和字符串s的最长公共前缀的长度，就是$z[n]$的值。

$z[0]=0$,这不必再多说了。

$z[1]=0$,因为字符串s和s的以第1项开头的后缀bacaba显然没有公共前缀，因此最长公共前缀为$0$，$z[1]=0$。

$z[4]=3$,字符串s的以第4项开头的后缀aba和字符串s的前三项相同，因此最长公共前缀为$3$，$z[4]=3$。

$贰.$计算Z函数

关于如何得到一个字符串的Z函数，可分为朴素算法（时间复杂度为$O(n^2)$)和线性算法。

（1）朴素算法

朴素算法即为暴力枚举后缀，然后暴力逐字符对比求得最长公共前缀。暴力总会出奇迹的。

  string s;
  /**
  在这里对s赋值
  **/
  int n = (int)s.length(); 
  vector<int> z(n);
  for (int i = 1; i < n; ++i)
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];

（2）线性算法

线性算法利用自动机的原理求取Z函数，如果不知道什么是自动机，还是直接背代码较好。 原理在文章末尾的注释中，若较感兴趣，可以一看。

  string s;
  /**
  还是在这里对s赋值
  **/
  int n = (int)s.length();
  vector<int> z(n);
  for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i <= r && z[i - l] < r - i + 1) {
      z[i] = z[i - l];
    } else {
      z[i] = max(0, r - i + 1);
      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;
  }

未完待续……