洛谷-P4287 双倍回文(回文自动机)

双倍回文

刚刚用Manacher写了一遍这个题，现在换种写法，舒服！！！优美的half数组求法
（Manacher的简单写法请走这里)

题意：若一个回文串左半部分和右半部分分别为一个回文串，则这个回文串被称为双倍回文串(这名字有点傻呀！)。求：给定一个回文串，问最长的双倍回文串有多长。

思路：

1. 由于双倍回文串是建立在回文串的基础上的，因此我们只需要对回文串动动手脚就行了
2. 首先建好回文自动机
3. 然后对每个节点跑一遍fail，若有一个len[fail]长度为len的一半，且len为4的倍数，那就更新答案咯
4. 显然，这样会被卡，aaaaaaaa…aaa这组数据就a不过呀！
5. 这时我们可以考虑倍增加速，比如先预处理好不超过当前回文长度一半长的回文后缀(命名为half)；并且可以以一种优美的方式得到。
6. 若一开始得到的fail[np]不是要求的half[np]
7. 则与求普通的fail类似，不过第一步先直接跳到之前求出的最长回文后缀(不包括自身的那个)的half上，然后循环找到能与自身形成更长回文串且不超过当前回文长度一半的hp，此时与求普通fail类似，令ch[hp][c]为half[np]即可
8. 最后就是遍历所有的节点更新答案啦

题目描述(由于题干使用太多LaTeX，不方便复制，所以。。。)

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 5e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;

char s[maxn];
int last, sz, pos;
int ch[maxn][26], fail[maxn], len[maxn], ans;
int half[maxn];

void init() {
    fail[0]=fail[1]=sz=last=1;
    len[1]=pos=-1;
}

void add(int c) {
    ++pos; int p=last;
    while(s[pos-len[p]-1]!=s[pos]) p=fail[p];
    if(!ch[p][c]) {
        int np=++sz, fp=fail[p];
        len[np]=len[p]+2;
        while(s[pos-len[fp]-1]!=s[pos]) fp=fail[fp];
        fail[np]=ch[fp][c];
        ch[p][c]=np;

        if(len[fail[np]]<=len[np]/2) half[np]=fail[np]; //如下if、else优美的求出了half数组
        else {
            int hp=half[p];
            while(len[hp]+2>len[np]/2||s[pos]!=s[pos-len[hp]-1]) hp=fail[hp];
            half[np]=ch[hp][c];
        }
        if(len[np]>ans&&len[np]%4==0&&len[half[np]]==len[np]/2) ans=max(ans,len[np]);//每个都判定一下更新答案
    }
    last=ch[p][c];
}

int main() {
	//ios::sync_with_stdio(false);
    int n=read();
    scanf("%s", s);
    init();
    for(int i=0; s[i]; ++i) add(s[i]-'a');
    cout<<ans<<endl;
}