看懂题意,看懂题意,看懂题意
开始没看懂题意,WA到崩溃
题目给一个字符串S,要你求最长的T
T:S的子串,并且T是两个回文串的拼接
BZOJ上样例的解释:
S=baacaabbacabb
从S的第二个字符开始到S的最后一个字符结束的子串 T=aacaabbacabb
T可分为aacaa与bbacabb两部分,且两者都是回文串,并且这也是满足条件的最长的T。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define max(a,b) a>b?a:b
const int maxn=100000+100;
int tree[maxn][26],len[maxn],fail[maxn],tot,suff;
int Maxlen[maxn][2];
char ch[maxn];
inline void insert(int pos){
int ind=ch[pos]-'a';
int cur=suff;
int curlen=len[suff];
while(true){
int locate=pos-1-curlen;
if(locate>=0 && ch[locate]==ch[pos]) break;
cur=fail[cur];
curlen=len[cur];
}
if(tree[cur][ind]){
suff=tree[cur][ind];
return;
}
tree[cur][ind]=++tot;
len[tot]=len[cur]+2;
suff=tot;
if(cur==0){
fail[tot]=1;
return;
}
while(true){
cur=fail[cur];
curlen=len[cur];
int locate=pos-1-curlen;
if(locate>=0 && ch[locate]==ch[pos]){
fail[tot]=tree[cur][ind];
break;
}
}
}
void init(){
tot=suff=1;
memset(tree,0,sizeof(tree));
len[0]=-1,len[1]=0;
fail[0]=0,fail[1]=0;
}
int main(){
init();
scanf("%s",ch);
int n=strlen(ch);
for(int i=0;i<n;i++) insert(i),Maxlen[i][0]=len[suff];
init();
for(int i=0;i<n/2;i++) swap(ch[i],ch[n-i-1]);
for(int i=0;i<n;i++) insert(i),Maxlen[n-i-1][1]=len[suff];
int Max=0;
for(int i=0;i<n-1;i++) Max=max(Max,Maxlen[i][0]+Maxlen[i+1][1]);
printf("%d\n",Max);
}