【luoguP4287】[SHOI2011]双倍回文

这是一个PAM的模板题
考虑一个子串成为双倍回文的条件,长度一定为4的倍数,并且沿着fail指针跳一定能跳到一个长度为其二分之一的子串。
那么就建出一个PAM就行,注意有两个根,一个是长度为偶数的回文串,一个是奇数的,找fail指针的时候,之所以是p-len-1,是因为你要考虑从原来p-1出发,往前跳len格正好到对应位置。建法挺像ACAM的。

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 5e5 + 10;

char s[ms];

int n, ans;

struct Pam
{
    int ne[ms], f[ms], len[ms], ch[ms][26], tot, las;

    inline int askfail(int x, int p)
    {
        while(s[p] != s[p - len[x] - 1])
            x = ne[x];
        return x;
    }

    inline void insert(int c, int p)
    {
        int no, Fa = askfail(las, p);
        if(!ch[Fa][c])
        {
            ne[no = ++ tot] = ch[askfail(ne[Fa], p)][c];
            len[no] = len[Fa] + 2, ch[Fa][c] = no;
            if(len[ne[no]] <= (len[no] >> 1))
                f[no] = ne[no];
            else
            {
                int P = f[Fa];
                while((len[P] + 2) > (len[no] >> 1) || s[p] != s[p - len[P] - 1])
                    P = ne[P];
                f[no] = ch[P][c];
            }
        }
        las = ch[Fa][c];
    }

    inline void build()
    {
        len[ne[0] = ++ tot] = -1;
        for(ri i = 1; i <= n; i ++)
            insert(s[i] - 'a', i);
    }

    inline void ask()
    {
        for(ri i = 1; i <= tot; i ++)
            if((!(len[i] & 3)) && len[f[i]] == (len[i] >> 1))
                ans = max(ans, len[i]);
    }
}pam;

int main()
{
    re(n), scanf("%s", s + 1);
    pam.build(), pam.ask();
    printf("%d", ans);
    system("pause");
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注