洛谷-P4287 双倍回文(Manacher)

双倍回文

Manacher算法用的还是不够熟悉啊，被卡了好久。。。一会再写个回文自动机的做法吧
清晰的回文自动机写法

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

思路：

1. 由于双倍回文串是建立在回文串的基础上的，因此我们只需要对回文串动动手脚就行了
2. 思考：若在Manacher算法处理好字符串后再对回文串进行判定，由于算法得到的p数组是当前位置能向两边拓展的最长回文串，因此为了遍历所有的回文串，必须将每个位置的p向下枚举；但这样势必造成一些重复枚举（其实不重要），比如当前回文串被包含在一个更长的回文串，且在其右半部分，则显然左半部分已经枚举过跟当前回文串一样的回文串的p
3. 为了舍弃这样的重复的枚举，我们采取在构建p数组的过程中进行双倍回文串的判定
4. 显然，只有在算法中i+p[i]>r即当前回文串右侧突破的最远右边界，当前回文串才不是被枚举过的，也就是说它需要被判定一下是否为双倍回文串。这样，算法复杂度就达到了O(n)
5. 最后是判定过程，建议在草稿纸上随便画画，然后细节就明了了

题目描述(由于题干使用太多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 = 1e6+10;
const int mod = 1e9+7;
const double eps = 1e-9;

char s[maxn], s0[maxn];
int p[maxn];

int change() {
    int len=strlen(s0);
    s[0]='?', s[1]='#';
    int j=2;
    for(int i=0; i<len; ++i) s[j++]=s0[i], s[j++]='#';
    s[j]='!';
    return j;
}

int Manacher() {
    int len=change(), mid=1, r=1, ans=0;
    for(int i=1; i<len; ++i) {
        if(i<r) p[i]=min(r-i,p[mid*2-i]);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]]) {
            p[i]++;
            if(r<i+p[i]&&s[i]=='#'&&(p[i]-1)%4==0) { //突破右边界才判定
                if(p[i-(p[i]-1)/2]-1>=(p[i]-1)/2) ans=max(ans,p[i]-1);
            }
        }
        if(r<i+p[i]) mid=i, r=i+p[i];
    }
    return ans;
}

int main() {
	//ios::sync_with_stdio(false);
    int n=read();
	scanf("%s", s0);
    cout<<Manacher()<<endl;
}