题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5371
题意：把一个数字串A翻过来（abc翻过来为cba）的操作为-A，我们称A-AA这样的串为N-sequence，现在给你一个数字串，问你这个串中最长的N-sequence子串长度
解：可以想到A-A是一个回文串，-AA也是一个回文串，那么首先Manacher跑一遍求出所有回文子串
可以想到任意两个互相覆盖串中心点的回文子串都可以表示成N-sequence
然后大概有三种搞法：
1、时间复杂度O(N*logN)，官方题解的方法。
将回文子串以从长到短的顺序加到一个set中（插入值为回文子串的中心位置），插入每个串前询问，该串覆盖范围内离它最远的子串中心位置，来更新答案（因为是从长到短插入set的，所以如果后来的串覆盖了某中心，那么该中心所代表的串一定覆盖后来的串
加了一点注释在代码里面~
2、时间复杂度O(N*logN*logN)，比赛的时候写（shui）的。
用分治+rmq乱搞了~价值不大，具体可以看代码
3、时间复杂度O(N^2)。。。吓死了，这个确实有这样子的
有人N^2剪枝过的，有人用了姿势奇怪的线段树，目测理论复杂度O(N^2)
O(N*logN)版本：
/*
* Problem: hdu5371 Hotaru's problem
* Author: SHJWUDP
* Created Time: 2015/8/11 星期二 12:25:41
* File Name: 1006.cpp
* State: Accepted
* Memo: Data struct
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set> using namespace std; int N;
vector<int> arr;
namespace Manacher {
/**
* "abacd\0" -> "$#a#b#a#c#d#\0"
*/
vector<int> arr, p; int go(vector<int> & A) {
int len=A.size();
arr.resize(A.size()*+);
p.resize(A.size()*+);
for(int i=len-; i>=; i--) {
arr[i*+]=A[i];
arr[i*+]=-;
}
arr[len*+]=-;
arr[len*+]=-;
arr[]=-;
len=len*+; ///闭区间
int maxp=, id;
for(int i=; i<len-; i++) {
if(i<maxp) p[i]=min(maxp-i, p[id-(i-id)]);
else p[i]=;
while(arr[i-p[i]]==arr[i+p[i]]) p[i]++;
if(i+p[i]>maxp) {
maxp=i+p[i];
id=i;
}
} //可以打印一下p数组，观察下~
vector<pair<int, int> > tmpArr; //pair(回文串长度， 回文串中心位置)
for(int i=; i<len-; i++) {
if(arr[i]!=- || p[i]<=) continue;
tmpArr.push_back(make_pair(p[i], i));
}
sort(tmpArr.begin(), tmpArr.end(), greater<pair<int, int> >()); //按回文串长从大到小排序
set<int> S;
int res=;
for(auto & x : tmpArr) {
//找当前串左侧覆盖的回文串中心
int lim1=x.second-(x.first-); //左侧
auto it1=S.lower_bound(lim1);
if(it1!=S.end() && lim1<=(*it1) && (*it1)<x.second) {
res=max(res, (x.second-(*it1))/*);
}
//找当前串右侧覆盖的回文串中心
int lim2=x.second+(x.first-); //右侧
auto it2=S.upper_bound(x.second+(x.first-));
if(it2!=S.begin()) --it2;
if(it2!=S.end() && x.second<(*it2) && (*it2)<=lim2) {
res=max(res, ((*it2)-x.second)/*);
}
S.insert(x.second);
}
return res;
}
void print() {
for(int i=; i<(int)arr.size(); i++) {
cout<<i<<"\t\n"[i==(int)arr.size()-];
}
for(int i=; i<(int)arr.size(); i++) {
cout<<arr[i]<<"\t\n"[i==(int)arr.size()-];
}
for(int i=; i<(int)arr.size(); i++) {
cout<<p[i]<<"\t\n"[i==(int)arr.size()-];
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
// freopen("out", "w", stdout);
#endif
int T, now=;
scanf("%d", &T);
while(T--) {
scanf("%d", &N);
arr.resize(N);
for(int i=; i<N; i++) {
scanf("%d", &arr[i]);
}
printf("Case #%d: ", ++now);
printf("%d\n", Manacher::go(arr));
}
return ;
}
O(N*logN*logN)版本：
/*
* Problem:
* Author: SHJWUDP
* Created Time: 2015/8/11 星期二 12:25:41
* File Name: 1006.cpp
* State:
* Memo:
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm> using namespace std; const int INF=0x7f7f7f7f; const int MaxA=2e6+; struct RMQ {
int d[MaxA][];
void init(const vector<int> & A, int n) {
for(int i=; i<n; i++) d[i][]=A[i];
for(int j=; (<<j)<=n; j++) {
for(int i=; i+(<<j)-<n; i++) {
d[i][j]=max(d[i][j-], d[i+(<<(j-))][j-]);
}
}
}
int query(int L, int R) {
int k=;
while((<<(k+)) <= R-L+) k++;
return max(d[L][k], d[R-(<<k)+][k]);
}
}; int N;
vector<int> arr(MaxA);
namespace Manacher {
/**
* "abacd\0" -> "$#a#b#a#c#d#\0"
*/
vector<int> arr(MaxA), p(MaxA), tmpArr(MaxA);
RMQ rmq; int dc(int lft, int rgt, int x) {
if(lft>=rgt) return lft;
int mid=(lft+rgt)>>;
int res=-;
if(rmq.query(lft, mid)>=x) res=dc(lft, mid, x);
else if(mid+<=rgt && rmq.query(mid+, rgt)>=x) res=dc(mid+, rgt, x);
return res;
} int go(vector<int> & A) {
int len=N, lim=len*+;
for(int i=len-; i>=; i--) {
arr[i*+]=A[i];
arr[i*+]=-;
}
arr[len*+]=-;
arr[len*+]=-;
arr[]=-;
len=len*+; ///闭区间
int maxp=, id;
for(int i=; i<len-; i++) {
if(i<maxp) p[i]=min(maxp-i, p[id-(i-id)]);
else p[i]=;
while(arr[i-p[i]]==arr[i+p[i]]) p[i]++;
if(i+p[i]>maxp) {
maxp=i+p[i];
id=i;
}
} for(int i=; i<lim; i++) {
if(arr[i]!=-) {
tmpArr[i]=-INF;
} else {
tmpArr[i]=i+p[i]-;
}
// cout<<tmpArr[i]<<" \n"[i==(int)p.size()-1];
} rmq.init(tmpArr, lim);
int res=;
for(int i=; i<len-; i++) {
if(arr[i]!=- || p[i]<=) continue;
// cout<<"to "<<i<<endl;
int lft=i-(p[i]-), rgt=i-;
int tmp=dc(lft, rgt, i);
// cout<<"tmp: "<<tmp<<endl;
if(tmp!=-) res=max(res, (i-tmp+)/*);
}
return res;
}
void print() {
for(int i=; i<(int)arr.size(); i++) {
cout<<i<<"\t\n"[i==(int)arr.size()-];
}
for(int i=; i<(int)arr.size(); i++) {
cout<<arr[i]<<"\t\n"[i==(int)arr.size()-];
}
for(int i=; i<(int)arr.size(); i++) {
cout<<p[i]<<"\t\n"[i==(int)arr.size()-];
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
// freopen("out", "w", stdout);
#endif
int T, now=;
scanf("%d", &T);
while(T--) {
scanf("%d", &N);
for(int i=; i<N; i++) {
scanf("%d", &arr[i]);
}
printf("Case #%d: ", ++now);
printf("%d\n", Manacher::go(arr));
}
return ;
}