HDU 5421 Victor and String(回文树)

Victor and String

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/262144 K (Java/Others)

Total Submission(s): 163    Accepted Submission(s): 78

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  times. Each time he will do one of following four operations. Operation 1 : add a char  to the beginning of the string. Operation 2 : add a char  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.

Input

The input contains several test cases, at most  cases. In each case, the first line has one integer  means the number of operations. The first number of next  line is the integer , meaning the type of operation. If = or , there will be a lowercase English letters followed. .

Output

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

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

Sample Output

4
5
4
5
11
这道题目和简单的回文树应用不一样了,它是在两头加字符,不是从左到右只加一边。那么我们怎么解决这样的问题呢?首先s[]数组应该开到长度的两倍,然后以中间作为起始点,分别向两边扩展。然后last应该有两个指针,一个指向左边,一个指向右边另外也应该有两个指针表示两边数组的长度,距离中间的长度在加入新节点的时候,从左边插,和从右边插是一样的,只是有一点在插入一边的时候可能会应该回影响另一边的last指针。具体见代码#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
typedef long long int LL;
const int MAX=1e5+5;
char str[MAX];
int n;
struct Tree
{
    int next[2*MAX][26];
    int fail[2*MAX];
    int num[2*MAX];
    int len[2*MAX];
    int s[2*MAX];
    int last[2];
    int tot[2];
    LL p;
    int new_node(int x)
    {
        memset(next[p],0,sizeof(next[p]));
        num[p]=0;
        len[p]=x;
        return p++;
    }
    void init()
    {
        p=0;
        new_node(0);
        new_node(-1);
        last[0]=0;
        last[1]=0;
        tot[0]=MAX-5;
        tot[1]=MAX-6;
        fail[0]=1;
    }
    int get_fail(int x,int k)
    {
        s[tot[0]-1]=-1;s[tot[1]+1]=-1;
         while(s[tot[k]]!=s[tot[k]+(k?-1:1)*(len[x]+1)])
            x=fail[x];
         return x;
    }
    int add(int x,int k)
    {
        x-='a';
        s[tot[k]+=(k?1:-1)]=x;
        int cur=get_fail(last[k],k);
        if(!(last[k]=next[cur][x]))
        {
            int now=new_node(len[cur]+2);
            fail[now]=next[get_fail(fail[cur],k)][x];
            next[cur][x]=now;
            num[now]=num[fail[now]]+1;
            last[k]=now;
            if(len[last[k]]==tot[1]-tot[0]+1)  last[k^1]=last[k];
        }
        return num[last[k]];
    }
}tree;
int main()
{
    int x;char y[10];
    while(scanf("%d",&n)!=EOF)
    {
        tree.init();
        LL ans=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            if(x==1)
            {
                scanf("%s",y);
                ans+=tree.add(y[0],0);
            }
            else if(x==2)
            {
                scanf("%s",y);
                ans+=tree.add(y[0],1);
            }

            else if(x==3)
                printf("%d\n",tree.p-2);
            else
                printf("%lld\n",ans);
        }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ3671: [Noi2014]随机数生成器(贪心)

第1行包含5个整数,依次为 x_0,a,b,c,d ,描述小H采用的随机数生成算法所需的随机种子。第2行包含三个整数 N,M,Q ,表示小H希望生成一个1到 N...

812
来自专栏算法修养

PAT 甲级 1060 Are They Equal

1060. Are They Equal (25) 时间限制 50 ms 内存限制 65536 kB 代码长度限制 16000 B ...

2935
来自专栏鸿的学习笔记

Python的函数

装饰器可以理解为输入一个函数返回一个新的函数的函数,python的装饰器是闭包的语法糖。

813
来自专栏python学习路

六、面向对象进阶

生成器 1、什么是生成器 生成器是这样一个函数,它记住上一次返回时在函数体中的位置。对生成器函数的第二次(或第 n 次)调用跳转至该函数中间,而上次调用的所有局...

3084
来自专栏calmound

UVA Hangman Judge

英语太烂啊。 In ``Hangman Judge,'' you are to write a program that judges a series of ...

3297
来自专栏ml

poj------2406 Power Strings

A - Power Strings 难度:☆☆ Time Limit:3000MS     Memory Limit:65536KB     64bit I...

3128
来自专栏LeetCode

LeetCode SingleNumber I,II,III

Given a non-empty array of integers, every element appears twice except for one....

1930
来自专栏计算机视觉与深度学习基础

Leetcode 238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such th...

1839
来自专栏算法修养

HDU 3333 Turing Tree (线段树)

Turing Tree Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768...

3488
来自专栏三好码农的三亩自留地

5分钟彻底理解-Java自动装箱、拆箱

当表格中左边列出的基础类型与它们的包装类有如下几种情况时,编译器会自动帮我们进行装箱或拆箱.

3092

扫码关注云+社区

领取腾讯云代金券