即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

[HDU5421]Victor and String-回文树

编程语言 zlttttt 9℃ 0评论
本文目录
[隐藏]

1.Problem Description

Victor loves to play with string. He thinks a string is charming as the string is a palindromic string.


Victor wants to play n times. Each time he will do one of following four operations.

Operation 1 : add a char c to the beginning of the string.


Operation 2 : add a char c to the end of the string.


Operation 3 : ask the number of different charming substrings.


Operation 4 : ask the number of charming substrings, the same substrings which starts in different location has to be counted.

At the beginning, Victor has an empty string.

2.Input

The input contains several test cases, at most 5 cases.

In each case, the first line has one integer n means the number of operations.

The first number of next n line is the integer op, meaning the type of operation. If op=1 or 2, there will be a lowercase English letters followed.

1≤n≤100000.

3.Output

For each query operation(operation 3 or 4), print the correct answer.

4.Sample Input

6


1 a


1 b


2 a


2 c


3


4


8


1 a


2 a


2 a


1 a


3


1 b


3


4

5.Sample Output

4


5


4


5


11

6.Source

BestCoder Round #52 (div.1) ($)


喜(sang)闻(xin)乐(bing)见(kuang)的回文树…….


好吧咱还是更喜欢叫它PAM(Palindromic Automaton)~


思路:


回文树,恩。


然而,支持双端插入的回文树。


那么,使用两个last(咱用u),两个getfail(咱用find),正着插反着插……


然后?好像就没有然后了……

实现上,呃……


事实上和原版真的没啥区别。


前后插入嘛,就是一个在最前的last,一个在最后的last,每次getfail从原来的r-len[x]-1加上了l+len[x]+1,然后就没了……


注意一些小细节,比如咱的add里的最后两行~

#include
#include
#include
#include
#include

using namespace std;

#define yo puts("yoooooooooooooo~")

const int N=200010;

struct PAM
{
    int nxt[N][29],fa[N],len[N];
    int siz[N],s[N],u[2];
    int pool,l,r;
    long long tot;

    inline void init()
    {
        memset(siz,0,sizeof(siz));
        memset(len,0,sizeof(len));
        memset(nxt,0,sizeof(nxt));
        memset(s,-1,sizeof(s));

        tot=0;
        l=N>>1,r=l-1;
        u[0]=u[1]=1;

        pool=1;
        fa[0]=fa[1]=1;
        len[0]=0;
        len[1]=-1;
    }

    PAM(){init();}

    inline int find(int x,bool d)
    {
        if(d)while(s[r-len[x]-1]!=s[r])
            x=fa[x];
        else while(s[l+len[x]+1]!=s[l])
            x=fa[x];
        return x;
    }

    inline void add(int v,bool d)
    {
        if(d)
            s[++r]=v;
        else
            s[--l]=v;

        int last=find(u[d],d),now;
        if(!nxt[last][v])
        {
            fa[++pool]=nxt[find(fa[last],d)][v];
            len[pool]=len[last]+2;
            siz[pool]=siz[fa[pool]]+1;

            nxt[last][v]=pool;
        }

        now=nxt[last][v];
        tot+=siz[now];
        u[d]=now;

        if(len[now]==r-l+1)//warning
            u[d^1]=now;
    }

}koishi;

int n;

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        int op;
        char ch[4];
        koishi.init();

        while(n--)
        {
            scanf("%d",&op);

            if(op<3)
            {
                scanf("%s",ch);
                koishi.add(ch[0]-'a',op-1);
            }
            else if(op==3)
                printf("%d\n",koishi.pool-1);
            else
                printf("%lld\n",koishi.tot);
        }
    }

    return 0;
}

转载请注明:CodingBlog » [HDU5421]Victor and String-回文树

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情