bzoj2342

bzoj2342.cpp

#include <cstdio>
#include <algorithm>
const int N = 500000 * 2 + 9;
char s[N],r[N];
int n,len[N],fa[N],ans;
void init()
{
    len[0] = 0;
    for (int i = 1,mp = 0; i < n; ++i) {
        if (mp + len[mp] >= i)
            len[i] = std::min(mp + len[mp] - i,len[2 * mp - i]);
        for (; i - len[i] - 1 >= 0 && i + len[i] + 1 < n && s[i + len[i] + 1] == s[i - len[i] - 1]; ) ++len[i];
        if (i + len[i] > mp + len[mp]) mp = i;
    }
}
int getf(int x){return x == fa[x] ? x : fa[x] = getf(fa[x]);}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("2342.in","r",stdin);
    freopen("2342.out","w",stdout);
    #endif
    scanf("%d\n",&n);
    scanf("%s",r);
    int m = 0;
    s[m++] = '#';
    for (int i = 0; i < n; ++i) {
        s[m++] = r[i];
        s[m++] = '#';
    }
    //puts(s);
    n = m;
    init();
    for (int i = 0; i < n; ++i) fa[i] = (i + 1) / 2 * 2;
    for (int i = 4,j; i < n; i += 2) {
        for (j = getf(i - len[i] / 2); j + len[j] < i; j = fa[j]) fa[j] = getf(j + 1);
        if (j < i) ans = std::max(ans,i - j);
    }
    printf("%d\n",ans * 2);
}