Prefix Function: $\pi[i]$

给定一个字符串s的前缀函数$\pi_s(i)$定义为：子串s[0: i]的相等的真前缀与真后缀的最长长度

Ex, s = abcadabc

0 0 0 1 0 1 2 3

$\pi_s[0] = 0$, 规定$\pi[0] = 0$

$\pi_s1 = 0$, ab没有相等的真前缀和真后缀

$\pi_s[2] = 0$, abc没有相等的真前缀和真后缀

$\pi_s[3] = 1$, abca有相等的真前缀和真后缀a

$\pi_s[4] = 0$, abcad没有相等的真前缀和真后缀

$\pi_s[5] = 1$, abcada有相等的真前缀和真后缀a

$\pi_s[6] = 2$, abcadab有相等的真前缀和真后缀ab

$\pi_s[7] = 3$, abcadabc有相等的真前缀和真后缀abc

TODO: Brute force

Overservation 1:

$\pi[i]$和$\pi[i+1]$的差值最少为1，即$\pi[i+1] \leq \pi[i] +1$

Prefix Function: $\pi[i]$#