[CSP-X 2023 山东] 回文字符串

知识点

字符串、动态规划、最长公共前缀

解题思路

若两端块互为反转，可将这两块分别拆成单字符，成对字符相同，块数不会减少。因此求最大块数时，只需考虑两端块完全相同。令f[l]表示去掉两端各l个字符后剩余串的最大合法块数，允许把非空剩余串整体作为一个中间块。枚举最外层块长k，若左右长度k的块相同，则用2+f[l+k]更新。用最长公共前缀表LCP在O(1)时间精确判断子串相等。

正确性说明

反转块拆字符保持所有对称配对合法，故只考虑相同块不损失最优解。任意至少两块的方案都有唯一最外层块长k，去掉这两块后是更小的同心区间；反之，任意相同的左右块和内部合法方案均能组成合法分割。枚举全部k的转移因而充分必要。空区间为0块，非空中间整体为1块；最终不足2块即不满足n>1。

易错点

原题的“互为回文”指互相反转，不要求两块各自为回文；最大块数为1时输出NO；LCP表使用uint16_t，每项最多10000；本解法约需200MB，原卷内存512MiB。

复杂度

时间O(|S|²)，空间O(|S|²)。长度10000时LCP表为约200MB。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);string s;cin>>s;int n=s.size(),w=n+1,h=n/2;vector<uint16_t>lcp((size_t)w*w,0);for(int i=n-1;i>=0;--i)for(int j=n-1;j>i;--j)if(s[i]==s[j])lcp[(size_t)i*w+j]=lcp[(size_t)(i+1)*w+j+1]+1;vector<int>f(h+1,1);if(n%2==0)f[h]=0;for(int l=h-1;l>=0;--l){for(int k=1;k<=(n-2*l)/2;++k)if(lcp[(size_t)l*w+n-l-k]>=k)f[l]=max(f[l],2+f[l+k]);}if(f[0]<2)cout<<"NO\n";else cout<<"YES\n"<<f[0]<<'\n';}