蓝桥杯2024年第十五届决赛真题-最长回文前后缀

小明特别喜欢回文串，然而回文串太少见了，因此他定义了一个字符串的相同长度的、不相交的前缀和后缀是 “回文前后缀”，当且仅当这个前缀和后缀拼起来是个回文串。那么字符串 S = c₁c₂c₃, . . . , c_n 的 “最长回文前后缀” 的长度L(S ) 即为 arg maxxS _[1,x] = (S _[n−x+1,n])T 其中 S _{[i, j]} 表示 S 的一个子串 c_ic_i+1 . . . c_j，S^T 表示翻转 S 得到的字符串。

对于一个给定的字符串 S，小明希望对其进行改造使得 L(S′) 尽可能大。改造允许将字符串中一个任意长度的子串删除。比如删除 S = abcdebi jbba 中的子串 S _[3,5] 后 S 变成了 abbi jbba。

小明想知道改造后的新字符串 S′ 的 “最长回文前后缀” 的长度 L(S′) 最大是多少？

输入共 1 行，一个字符串 S。

输出共 1 行，一个整数表示答案。

abcdebijbba

3

【样例说明】

如题干中的方案删除 S _[3,5] 后，S′ = abbi jbba，L(S′) = 3。

【评测用例规模与约定】

对于 20% 的评测用例，保证 |S | ≤ 500。

对于 100% 的评测用例，保证 |S | ≤ 500000，S 仅包含小写字母。