Z函数

话说这玩意和 Kmp 有啥关系要把它称为扩展 Kmp。

P5410 【模板】Z函数

1. 一个串的 Z 函数

   因为代码中 i != 1，所以可以省去边界判断。

   int z[MAXn + 10];
   void EvaZ(char *str, int n) {
       z[1] = n;
       for (int i = 2, l = 0, r = 0; i <= n; ++i) {
           if (i <= r) z[i] = min(r - i + 1, z[i - l + 1]);
           while (str[i + z[i]] == str[1 + z[i]]) ++z[i];
           if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
       }
   }

2. 两个串的 Z 函数

   设文本串为 $t$，模式串为 $p$。相当于让 $s=p+\diamond+t$，求 $s$ 的 Z 函数。代码中定义了一个 Y 函数，省去了拼接操作，实际上做法是相同的，就是先求一下模式串的 Z 函数，再用一个 Y Box优化，文本串的 Y Box 和模式串的·前缀相同。

   int y[MAXn + 10];
   void EvaY(char *txt, char *wrd, int n, int m) {
       EvaZ(wrd, m);
       for (int i = 1, l = 0, r = 0; i <= n; ++i) {
           if (i <= r) y[i] = min(r - i + 1, z[i - l + 1]);
           while (i + y[i] <= n && 1 + y[i] <= m && txt[i + y[i]] == wrd[1 + y[i]]) ++y[i];
           if (i + y[i] - 1 > r) l = i, r = i + y[i] - 1;
       }
   }

3. 自己糊的奇葩做法

   既然可以先求模式串的 Z 函数，再用 Box 优化，为什么不能先求文本串的 Z 函数，再用 Box 优化呢？于是我糊了这个奇葩做法，Luogu 是可以过的，当然最劣复杂度……我没有算，应该是非线性的，所以考试时当然不要用。

   int y[MAXn + 10];
   void EvaY(char *txt, char *wrd, int n, int m) {
       z[1] = n;
       while (1 + y[1] <= n && 1 + y[1] <= m && txt[1 + y[1]] == wrd[1 + y[1]]) ++y[1];	
       for (int i = 2, l = 0, r = 0; i <= n; ++i) {
           if (i <= r) z[i] = min(r - i + 1, z[i - l + 1]);
   
           y[i] = min(z[i], y[i - l + 1]);
           while (i + y[i] <= n && 1 + y[i] <= m && txt[i + y[i]] == wrd[1 + y[i]]) ++y[i];
   
           while (txt[i + z[i]] == txt[1 + z[i]]) ++z[i];
           if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
       }
   }