hdu 5421 Victor and String

hdu 5421 Victor and String

支持双端插入的回文树。

考虑维护第二个 last 表示当前整个串的最长回文前缀。

往前 append 的时候可以直接那第二个 last 来跳 fail ， 因为回文前缀和回文后缀是对称的。只有 getfail 的时候需要改一下，变成判断当前字符和前缀之后的字符是否相同。

还要注意，如果当前的前面/后面 的 last 是整个串，那么需要把另一个 last 也设置成整个串。

注意如果当前插入得到的回文串pam里面已经有了也要加上它的贡献！

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 300006
int n;
struct pam {
    int son[MAXN][26] , fail[MAXN] , dep[MAXN] , len[MAXN] , s[MAXN * 3];
    int last[2] , n = 0 , st = 100006 , en = st , p = 0; long long re = 0;
    int newnode(int l) {
        for (int i = 0; i < 26; i++)
            son[p][i] = 0;
        len[p] = dep[p] = l;
        return p++;
    }
    void init( ) {
        memset( s , -1 , sizeof s );
        p = re = 0;
        newnode( 0 ) , newnode( -1 );
        st = en = 100006;
        last[0] = last[1] = n = 0;
        fail[0] = 1;
    }
    int getfail1( int u ) {
        while( s[en - len[u] - 1] != s[en] ) u = fail[u];
        return u;
    }
    int getfail2( int u ) {
        while( s[st + len[u] + 2] != s[st + 1] ) {
            u = fail[u];
        }
        return u;
    }
    void add( int u , bool af ) { 
        u -= 'a';
        int cur;
        if( af ) {
            s[++ en] = u;
            cur = getfail1( last[af] ); 
        }
        else s[st --] = u , cur = getfail2( last[af] );
        if( !son[cur][u] ) {
            int now = newnode( len[cur] + 2 );
            fail[now] = son[af ? getfail1(fail[cur]) : getfail2(fail[cur])][u];
            son[cur][u] = now;
            dep[now] = dep[fail[now]] + 1 , re += dep[now];
        } else re += dep[son[cur][u]];
        last[af] = son[cur][u];
        if( len[last[af]] == en - st ) last[af^1] = last[af];
    }
    int dif( ) {
        return p - 2;
    }
    long long und( ) {
        return re;
    }
} pam ;

int main() {
    int op; char ch[3];
    while( cin >> n ) {
        pam.init();
        while( n -- ) {
            scanf("%d",&op);
            if( op == 1 ) {
                scanf("%s",ch) , pam.add( ch[0] , 0 );
            } else if( op == 2 ) {
                scanf("%s",ch) , pam.add( ch[0] , 1 );
            } else if( op == 3 ) {
                printf("%d\n",pam.dif( ));
            } else printf("%lld\n" , pam.und());
        }
    }
}

hdu 5421 Victor and String

原文：https://www.cnblogs.com/yijan/p/hdu5421.html