KMP and Suffix Structure

感觉自己像个宝崽，不会的可真多

---

Prefix Function (Next or Fail or whatever the same name)

KMP里用到的z[i]（prefix function，z function和prefix function可以互相转换，名字借用一下）表示字符串0…i最长相同前后缀（看了很多grandmaster代码，所有人的习惯都不一样，天知道都是怎么想的=_+，我选择保持下标一致，z[i]表示最长长度)。

通过递推，用z[0]~z[i]算出$z[i+1]$，主要思想是第i+1个字母能不能和“之前已经匹配上的最长串的下一个字母”相匹配。如果不行，递归退回次长的串，再尝试匹配。这里有个很奇妙的性质，对于当前的串0~i，最长前后匹配串长度为$z[i]$，次长为$z[z[i] - 1]$…这个套娃背后的原理是：