Z 函数（扩展 KMP）

[Ir1d]

https://oi-wiki.org/string/z-func/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛竞赛

[weiyong1024]

为什么生成z函数的主循环从1开始迭代（不是0）

因为如果从0开始迭代算法将在第一次循环将匹配段[l, r]设置成[0, n - 1]，进而退化成O(n^2)的朴素版本

[Ir1d]

@weiyong1024 hi，有没有兴趣开个 Pull request 加到正文里面 😄

[weiyong1024]

@weiyong1024 hi，有没有兴趣开个 Pull request 加到正文里面

好滴~

[yangqianrui]

本质不同子串数哪个，O(n^2) 的复杂度有啥意义呢= =，暴力枚举子串+哈希也是 O(n^2) 的吧

[sshwy]

@yangqianrui
本质不同子串数哪个，O(n^2) 的复杂度有啥意义呢= =，暴力枚举子串+哈希也是 O(n^2) 的吧

并非只有最优复杂度的算法才有意义，只是提供一个应用的思路。如果您有更合适的例题应用欢迎参与贡献 🤔

[izlyforever]

先入为主的学了 前缀函数，Z 函数可以做为了解，没有特殊原因，应该是不会去使用了。

[izlyforever]

一个无关紧要的小优化：if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; 可以丢到 else 里面

[minghu6]

原来的那个说明和实现：

vector<int> z_function(string 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] = min(r - i + 1, z[i - l]);
    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;
}

挺好的为啥要改，思路非常清楚，能前面计算结果能利用的利用，剩下的朴素求解，最后更新边界。

还有复杂度证明里面的对内层while循环的分析，
++z[i]就是移动一位的意思，怎么改成了至少一位？ 至少一位是指外部for循环每次至少一位。

我认为修改的时候只是思路不同，而没有明显改进还是不要改了吧，否则每人都有自己的思路，rewrite无尽头呀。

还有我不得不吐槽一下，我想看看 @ouuan review @sshwy 的pr，或者反过来也可以，嗯，与其说我不觉得他们能互相通过，不如说我觉得他们一定互相都通不过。

ouuan：我是高手，我不愿多说话，理解不理解的，按我的来好吧。
sshwy：我有自己对细节的坚持（自己例外），我不管你思路是什么，通通rewrite掉，按我思路来。

（狗头保命）

[Tian-Xing]

原版写法进入while循环的次数多于新版写法，在1e7数据规模上常数会相比新版写法大很多，有些毒瘤出题人在卡哈希的时候可能会误卡掉这种常数大的写法，尤其是在杭电OJ这种评测机跑的比较慢的地方，实测2023杭电第八场1006使用常数较大的原版写法过不去，换成新版跑的跟std一样快。

[hly1204]

@minghu6
原来的那个说明和实现：

vector<int> z_function(string 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] = min(r - i + 1, z[i - l]);
    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;
}

挺好的为啥要改，思路非常清楚，能前面计算结果能利用的利用，剩下的朴素求解，最后更新边界。

还有复杂度证明里面的对内层while循环的分析，
++z[i]就是移动一位的意思，怎么改成了至少一位？ 至少一位是指外部for循环每次至少一位。

我认为修改的时候只是思路不同，而没有明显改进还是不要改了吧，否则每人都有自己的思路，rewrite无尽头呀。

还有我不得不吐槽一下，我想看看 @ouuan review @sshwy 的pr，或者反过来也可以，嗯，与其说我不觉得他们能互相通过，不如说我觉得他们一定互相都通不过。

ouuan：我是高手，我不愿多说话，理解不理解的，按我的来好吧。
sshwy：我有自己对细节的坚持（自己例外），我不管你思路是什么，通通rewrite掉，按我思路来。

（狗头保命）

其实我觉得新的这个思路更符合给出的解释，因为显式判断了无需再扩展的情况而不是以减少代码量为目的

[yan-qiu]

原文中如果z[i] > r错了吧，应该是如果i + z[i] - 1 > r

[Dfkuaid]

@yan-qiu
原文中如果z[i] > r错了吧，应该是如果i + z[i] - 1 > r

已修复~

[wangheyi2020]

z[i-l]>=r-i+1 那块，显然如果 z[i-l]>r-i+1，就一定不能再往后扩展，因为若 s[r+1]==s[i-l+1]，则 [l,r] 那段一定在 r+1 处也匹配，自相矛盾，所以只有 z[i-l]=r-i+1 的情况需要暴力检查，虽然实现上没有什么差别，也不影响复杂度，但是还是指明为好吧，严谨一些

[Yasong666]

z[i-l]>=r-i+1 那块，显然如果 z[i-l]>r-i+1，就一定不能再往后扩展，因为若 s[r+1]==s[i-l+1]，则 [l,r] 那段一定在 r+1 处也匹配，自相矛盾，所以只有 z[i-l]=r-i+1 的情况需要暴力检查，虽然实现上没有什么差别，也不影响复杂度，但是还是指明为好吧，严谨一些

你说的应该是s[r+1] == s[r-l+1] == s[r-i+1]吧。 不过确实是不用考虑z[i-l] > r -i +1这种情况。

[k8ysun]

第一个应用 匹配所有子串 里的k = |P|是否应该改成k >= |P|?

[hhc0001]

WD...这玩意该不是跟manacher一块生的

[Pinghigh]

太像了我去

[YoungCIoud]

在试图更新边界的时候感觉要 z[i] != 0 这个条件会好一点吧。