前缀等于后缀的最大长度：KMP模板--next数组

题目描述:

你需要求出字符串S中第1到i个字符组成的字符串前缀等于后缀的最大长度，注意该长度不等于i。

输入格式:

输入字符串长度N，再输入字符串S。保证串由小写字母构成。

输出格式:

输出N个数，第i个数代表字符串S中第1到i个字符组成的字符串前缀等于后缀的最大长度。

样例输入:

9 abababaac

样例输出:

0 0 1 2 3 4 5 1 0

提示:

kmp

 

N<=100000

时间限制: 1000ms
空间限制: 256MB

---

来源: by qq1010903229