备忘，讲讲思想
f[i]表示1到i最长的后缀等于前缀。容易证得每次f最多+1，然后复杂度就是O(n)的。匹配当成拼接在原串后面继续计算f数组。
z[i]表示i开始的最长的等于原串前缀的长度。暴力扩展是O(n^2)的，每次记录一个最右的等于某前缀的串[l, r]，i<=r就从min(r - i + 1, z[i - l + 1])开始扩展，否则从0开始。能证每次扩展r都要向右移动，所以复杂度O(n)
构建fail的基本思想是对于结点u往c走到达的子节点v，不断跳u = fail[u]，直到存在往c走的路，然后fail[v] = fail[ch[u][c]]。然而这一过程可以简化，某个点没有往c走的边，就连到fail往c走的边。这样补成trie图，就能线性时间完成计算。
AC自动机有很多好的性质。比如从u（对应串S）沿着ch一直走，每次得到的串T，S后缀和T前缀的最大重叠长度是递增的。
原文：https://www.cnblogs.com/hongzy/p/11299072.html