bzoj2565(最长双回文串记录每个位置的后缀最长回文串)

题目
正反两边PAM&＃xff0c;记录每个位置向左延伸向右延伸的最长回文串的长度。

#include
#include
#include
using namespace std;
const int N&＃61;1e5&＃43;5,Max&＃61;26;
//记录一个以i为下标结尾得最长的字符串的长度
struct PAM{int nex[N][26],fail[N],s[N],len[N],ans[N],las,tot,n;int newnode(int le){for(int i&＃61;0;i<Max;&＃43;&＃43;i) nex[tot][i]&＃61;0;len[tot]&＃61;le;return tot&＃43;&＃43;;}void init(){tot&＃61;0,newnode(0),newnode(-1);n&＃61;las&＃61;0,s[0]&＃61;-1,fail[0]&＃61;1;}int get_fail(int x){while(s[n-len[x]-1]!&＃61;s[n]) x&＃61;fail[x];return x;}void add(int c,int pos){c-&＃61;&＃39;a&＃39;,s[&＃43;&＃43;n]&＃61;c;int cur&＃61;get_fail(las);if(!nex[cur][c]){int now&＃61;newnode(len[cur]&＃43;2);fail[now]&＃61;nex[get_fail(fail[cur])][c];nex[cur][c]&＃61;now;}las&＃61;nex[cur][c],ans[pos]&＃61;len[las];//以pos这个位置的最长后缀回文串的长度为len[las]。}
}A,B;
char s[N];
int main(){scanf("%s",s&＃43;1);int len&＃61;strlen(s&＃43;1);A.init();for(int i&＃61;1;i<&＃61;len;&＃43;&＃43;i) A.add(s[i],i);//向左最长的后缀回文串B.init();for(int i&＃61;len;i>&＃61;1;--i) B.add(s[i],i);//向右最长的前缀回文串(倒过来就是后缀回文串哦)int res&＃61;0;for(int i&＃61;1;i<len;&＃43;&＃43;i) res&＃61;max(res,A.ans[i]&＃43;B.ans[i&＃43;1]);printf("%d\n",res);
}