ZOJ3807 Just a Palindrome
给定一个字符串，可以选择两个字符将其交换一次，求交换后的最长回文子串。
和Manacher一样的套路，因为回文串分奇数/偶数长度，所以把串扩充为$#1#2#3#…#$的形式来避免这种讨论。
求出一每个字符为中心的最长回文子串的最大长度后，考虑第一个不匹配的位置，左右两边分别记为$L , R$，此外再求出如果这一位也匹配了，得到的回文子串的长度。
这样一共就分三种情况。
- 从串的两端选择一个$L$或$R$与对应位置交换。匹配两段。
- 如果串长为奇数且中心字符是$L , R$之一，与其交换，匹配两段。
- 如果第二次得到的不匹配位置的字符为$R , L$，与第一次不匹配位置交换恰好让它都匹配上，这样就能匹配三段。
再举一些例子
- $acbab$、是以$cb$中心扩展时，以第一种方式交换为$abbac$的。
- $abb$、是以第一个b为中心时，以第二种方式交换为$bab$的。
- $aabcc$、是以b为中心时，以第三种方式交换为$acbca$的。
至于具体的求匹配回文长度，当然还是用hash方便啦，hash大法好。