Codeforces D1/D2. Prefix Suffix Palindrome (Manacher) /详解

D1. Prefix-Suffix Palindrome (Easy version) D2. Prefix-Suffix Palindrome (Hard version) 题意: 对于给出的字符串,可截取其前缀和后缀,求能组成的最长回文串。 思路: 正常来说暴力的思路是先匹配前缀pre和后缀suf,找到第一个不匹配的l和r,然后在由l开始从左向右求最长的回文串palindrome,以及由r开始从右向左求最长的回文串palindrome,那么pre+palindrome+suf就是答案。 很显然,这是一个O(n^2)时间复杂度的算法,那么还有哪里可以优化呢?其实关于求回文串palindrom