rt，应该是 $\mathcal{O}(n)$ 的，但是不知道怎么证 /kk

网上搜了搜没明白，有大佬能讲一下吗，感激不尽！

（代码供参考，方便讲解）

for (int i = 1; i < n; ++i) {
  int j = nxt[i];
  while (j && s[i] != s[j]) j = nxt[j];
  if (s[i] == s[j]) nxt[i + 1] = j + 1;
}