-1.参考资料
0.定义
本文中，字符串下标均从1开始，所以可能和 OI wiki 有一些出入。
定义(pi[i]) （前缀函数）表示 (s[1dots i]) 的最长公共前缀后缀的长度。
形式化的，有：
[pi[i]=max_{k=0dots i}{k|s[1dots k]=s[i-(k-1)dots i]}
]
特别的，(pi[1]=0)。
1.预处理
首先有一个显然的结论：
[pi[i+1]le pi[i]+1
]
原因是 (s[1dots pi[i+1]]=s[i-(pi[i+1]-1)dots i]) 可以推出 (s[1dots pi[i+1]-1]=s[i-(pi[i+1]-1)dots i-1])
令 (k=pi[i+1]-1) 即得 (s[1dots k]=s[i-1-(k-1)dots i-1])
根据 (pi[i]) 的定义即得 (pi[i]ge k=pi[i+1]-1)，得证。
于是考虑暴力枚举预处理，然后利用字符串哈希来判别字符串是否相等。
复杂度 (O(sum_{i=1}^{n-1}pi[i]+1-pi[i]-1)=O(n))。
但是这个算法不一定是正确的，可能会被卡模数，我们考虑继续优化。
首先根据上面那个结论我们可以得到一个推论，就是 (s[1dots pi[i+1]-1]=s[i-(pi[i+1]-1)dots i-1]) ，因此我们考虑枚举 (s[1dots i-1]) 的公共前缀后缀。
考虑怎么 (O(1)) 找到一个公共前缀后缀的前驱（i.e.仅次于这个公共前缀后缀的第二长度）。
设已知 (s[1dots j]=s[i-j+1dots i])，要求出 (max{j'|s[1dots j']=s[i-j'+1dots i],j'<j}) 。
有
[s[1dots j']=s[i-j'+1dots i]=s[j-j'dots j]
]
我们发现了
[s[1dots j']=s[j-j'dots j]
]
所以
[j'=pi[j]
]
Q.E.D.
转移的次数仍然是 (O(n)) 的，但是因为我们避免了字符串比较，所以总复杂度 (O(n)) 。
代码：
void init(char*s,int n,int*nxt){
nxt[1]=0;
for(int i=2,j;i<=n;i++){
while(j&&s[j+1]!=s[i])j=nxt[j];
if(s[i]==s[j+1])j++;
nxt[i]=j;
}
}