LGP4827 双倍回文 (PAM+tran数组)

记字符串\(w\)的倒置为\(w^R\)。例如\((abcd)^R=dcba，(abba)^R=abba\)

对字符串\(x\)，如果\(x\)满足\(x^R=x\) ，则称之为回文；例如\(abba\)是一个回文，而\(abed\)不是。

如果\(x\)能够写成的\(ww^Rww^R\)形式，则称它是一个“双倍回文”。换句话说，若要\(x\)是双倍回文，它的长度必须是\(4\)的倍数，而且\(x\)，\(x\)的前半部分，\(x\)的后半部分都要是回文。例如\(abbaabba\)是一个双倍回文，而\(abaaba\)不是，因为它的长度不是\(4\)的倍数。

\(x\)的子串是指在\(x\)中连续的一段字符所组成的字符串。例如\(be\)是\(abed\)的子串，而\(ac\)不是。

\(x\)的回文子串，就是指满足回文性质的\(x\)的子串。

\(x\)的双倍回文子串，就是指满足双倍回文性质的\(x\)的子串。

你的任务是，对于给定的字符串，计算它的最长双倍回文子串的长度。

\(PAM\).

维护 \(tran\)数组，\(tran[i]\)表示跳转到小于等于当前节点\(i\)一半长度的最长回文后缀。

构造方式与\(getfail\)相同，只是加了一个一半长度的限制。

最后统计一下符合 \(pam.len[pam.tran[i]]\mod 2==0 \and pam.len[pam.tran[i]]*2==pam.len[i]\)

条件的节点的最大长度即可。

时间复杂度\(O(n)\).