求出最長的子串可以分成兩個回文串
先處理出以每個位置為中心的最長回文子串，然後我是求了兩個這樣的數組left[] right[]，分別表示某位置往左最長的回文子串（以該位置結尾），右邊的雷同
需要線性掃兩遍。。。
處理這兩個數組的時候細節問題整了半天，所幸最後還是整出來了。
[cpp]
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn= 200010;
namespace M {
int n;
struct node {
int a,b;
int cen;
node() {}
node(int _a,int _b):a(_a),b(_b){};
bool operator < (const node&cmp) const {
return b < cmp.b;
}
}in[maxn];
vector<pair<int,int> > P[maxn] ;
/// P[i]記錄以i為中心的所有的最長回文子串（其實最多只有兩個,奇偶性。。）
int left[maxn] , right[maxn];
bool ji[maxn];
void solve()
{
memset(ji,false,sizeof(ji));
int mx = 0;
for(int i = 0; i < n; i++)mx = max(mx,in[i].b);
for(int i = 1; i <= mx; i++) P[i].clear();
for(int i = 0; i < n; i++)
{
in[i].cen= in[i].a+in[i].b >> 1;
P[in[i].cen].push_back(make_pair(in[i].a,in[i].b));
}
int pt = 1;
for(int i = 1; i <= mx; i++)
{
for(; pt < i; pt++)
{
int a = P[pt][0].first;
int b = P[pt][0].second;
if(b>=i)
{
ji[i] = true;
break;
}
if(P[pt].size()==1) continue;
a = P[pt][1].first;
b = P[pt][1].second;
if(b>=i)
{
break;
}
}
left[i] = pt;
}
for(int i = 1; i <= mx; i++)
{
left[i] = max(1,(i - left[i])*2+ji[i]);
}
pt = mx;
memset(ji,false,sizeof(ji));
for(int i = mx; i >= 1; i--)
{
right[i] = i;
for(; pt >= i; pt--)
{
int a, b;
if(P[pt].size() > 1)
{
a = P[pt][1].first;
b = P[pt][1].second;
if(a<=i)
{
right[i] = pt + 1;
break;
}
}
a = P[pt][0].first;
b = P[pt][0].second;
if(a<=i)
{
right[i] = pt;
ji[i] = true;
break;
}
}
}
for(int i = 1; i <= mx; i++)
{
right[i] = max(1,(right[i] - i)*2+ji[i]);
}
int ans = 0;
for(int i = 1; i < mx; i++)
{
ans = max(ans,left[i]+right[i+1]);
}
printf("%d\n",ans);
}
}
struct Mancher {
char str[maxn];//start from index 1
int p[maxn];
char s[maxn];
int n;
void checkmax(int &ans,int b){
if(b>ans) ans=b;
}
inline int min(int a,int b){
return a<b?a:b;
}
void kp(){
int i;
int mx = 0;
int id;
for(i=1; i<n; i++){
if( mx > i )
p[i] = min( p[2*id-i], p[id]+id-i );
else
p[i] = 1;
for(; str[i+p[i]] == str[i-p[i]]; p[i]++) ;
if( p[i] + i > mx ) {
mx = p[i] + i;
id = i;
}
}
}
void pre()
{
int i,j,k;
n = strlen(s);
str[0] = '$';
str[1] = '#';
for(i=0;i<n;i++)
{
str[i*2 + 2] = s[i];
str[i*2 + 3] = '#';
}
n = n*2 + 2;
str[n] = 0;
}
void solve() // 求出所有的最長回文子串所在的區間
{
int & tot = M::n;
tot = 0;
for(int i = 2; i < n; i++)
{
if(i%2&&p[i]==1) continue;
if(i%2)
{
M::in[tot++] = M::node(i/2-p[i]/2+1,i/2+p[i]/2);
//printf("%d %d\n",i/2-p[i]/2+1,i/2+p[i]/2);
}
else
{
M::in[tot++] = M::node(i/2-(p[i]/2-1),i/2+(p[i]/2-1));
//printf("%d %d\n",i/2-(p[i]/2-1),i/2+(p[i]/2-1));
}
}
}
}task1;
int main()
{
while( scanf("%s", task1.s) !=EOF )
{
task1.pre();
task1.kp();
task1.solve();
M::solve();
}
return 0;
}
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn= 200010;
namespace M {
int n;
struct node {
int a,b;
int cen;
node() {}
node(int _a,int _b):a(_a),b(_b){};
bool operator < (const node&cmp) const {
return b < cmp.b;
}
}in[maxn];
vector<pair<int,int> > P[maxn] ;
/// P[i]記錄以i為中心的所有的最長回文子串（其實最多只有兩個,奇偶性。。）
int left[maxn] , right[maxn];
bool ji[maxn];
void solve()
{
memset(ji,false,sizeof(ji));
int mx = 0;
for(int i = 0; i < n; i++)mx = max(mx,in[i].b);
for(int i = 1; i <= mx; i++) P[i].clear();
for(int i = 0; i < n; i++)
{
in[i].cen= in[i].a+in[i].b >> 1;
P[in[i].cen].push_back(make_pair(in[i].a,in[i].b));
}
int pt = 1;
for(int i = 1; i <= mx; i++)
{
for(; pt < i; pt++)
{
int a = P[pt][0].first;
int b = P[pt][0].second;
if(b>=i)
{
ji[i] = true;
break;
}
if(P[pt].size()==1) continue;
a = P[pt][1].first;
b = P[pt][1].second;
if(b>=i)
{
break;
}
}
left[i] = pt;
}
for(int i = 1; i <= mx; i++)
{
left[i] = max(1,(i - left[i])*2+ji[i]);
}
pt = mx;
memset(ji,false,sizeof(ji));
for(int i = mx; i >= 1; i--)
{
right[i] = i;
for(; pt >= i; pt--)
{
int a, b;
if(P[pt].size() > 1)
{
a = P[pt][1].first;
b = P[pt][1].second;
if(a<=i)
{
right[i] = pt + 1;
break;
}
}
a = P[pt][0].first;
b = P[pt][0].second;
if(a<=i)
{
right[i] = pt;
ji[i] = true;
break;
}
}
}
for(int i = 1; i <= mx; i++)
{
right[i] = max(1,(right[i] - i)*2+ji[i]);
}
int ans = 0;
for(int i = 1; i < mx; i++)
{
ans = max(ans,left[i]+right[i+1]);
}
printf("%d\n",ans);
}
}
struct Mancher {
char str[maxn];//start from index 1
int p[maxn];
char s[maxn];
int n;
void checkmax(int &ans,int b){
if(b>ans) ans=b;
}
inline int min(int a,int b){
return a<b?a:b;
}
void kp(){
int i;
int mx = 0;
int id;
for(i=1; i<n; i++){
if( mx > i )
p[i] = min( p[2*id-i], p[id]+id-i );
else
p[i] = 1;
for(; str[i+p[i]] == str[i-p[i]]; p[i]++) ;
if( p[i] + i > mx ) {
mx = p[i] + i;
id = i;
}
}
}
void pre()
{
int i,j,k;
n = strlen(s);
str[0] = '$';
str[1] = '#';
for(i=0;i<n;i++)
{
str[i*2 + 2] = s[i];
str[i*2 + 3] = '#';
}
n = n*2 + 2;
str[n] = 0;
}
void solve() // 求出所有的最長回文子串所在的區間
{
int & tot = M::n;
tot = 0;
for(int i = 2; i < n; i++)
{
if(i%2&&p[i]==1) continue;
if(i%2)
{
M::in[tot++] = M::node(i/2-p[i]/2+1,i/2+p[i]/2);
//printf("%d %d\n",i/2-p[i]/2+1,i/2+p[i]/2);
}
else
{
M::in[tot++] = M::node(i/2-(p[i]/2-1),i/2+(p[i]/2-1));
//printf("%d %d\n",i/2-(p[i]/2-1),i/2+(p[i]/2-1));
}
}
}
}task1;
int main()
{
while( scanf("%s", task1.s) !=EOF )
{
task1.pre();
task1.kp();
task1.solve();
M::solve();
}
return 0;
}
