URAL 2040 Palindromes and Super Abilities 2(回文树)

Palindromes and Super Abilities 2

Time Limit: 1MS

Memory Limit: 102400KB

64bit IO Format: %I64d & %I64u

Status

Description

Dima adds letters s1, …, sn one by one to the end of a word. After each letter, he asks Misha to tell him how many new palindrome substrings appeared when he added that letter. Two substrings are considered distinct if they are different as strings. Which nnumbers will be said by Misha if it is known that he is never wrong?

Input

The input contains a string s1 … sn consisting of letters ‘a’ and ‘b’ (1 ≤ n ≤ 5 000 000).

Output

Print n numbers without spaces: i-th number must be the number of palindrome substrings of the prefix s1 … si minus the number of palindrome substrings of the prefixs1 … si−1. The first number in the output should be one.

Sample Input

input

output

abbbba

111111

Source

Problem Author: Mikhail Rubinchik (prepared by Kirill Borozdin)  Problem Source: Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014 

每插入一个字符都会有两种情况,产生新的回文树节点,不产生新的节点。所以答案只会是0,1

#include <iostream>
#include <string.h>

#include <stdlib.h>
#include <math.h>
#include <stdio.h>

using namespace std;
typedef long long int LL;
const int MAX=5*1e6;
const int maxn=4*1e6+5;
char str[MAX+5];
struct Tree
{
    int next[maxn][2];
    int fail[MAX+5];
    int len[MAX+5];
    int s[MAX+5];
    int last,n,p;
    int new_node(int x)
    {
        memset(next[p],0,sizeof(next[p]));
        len[p]=x;
        return p++;
    }
    void init()
    {
        p=0;
        new_node(0);
        new_node(-1);
        last=0;n=0;
        s[0]=-1;
        fail[0]=1;
	}
    int get_fail(int x)
    {
        while(s[n-len[x]-1]!=s[n])
            x=fail[x];
        return x;
    }
    int add(int x)
    {
        x-='a';
        s[++n]=x;
        int cur=get_fail(last);
        if(!(last=next[cur][x]))
        {
            int now=new_node(len[cur]+2);
            fail[now]=next[get_fail(fail[cur])][x];
            next[cur][x]=now;
            last=now;
            return 1;
        }
        return 0;
    }

}tree;
char ans[MAX+5];
int main()
{
    while(scanf("%s",str)!=EOF)
    {
       
        tree.init();
		int i;
        for( i=0;str[i];i++)
        {
			if(!tree.add(str[i]))
			    ans[i]='0';
			else
				ans[i]='1';
		}
		ans[i]='\0';
		puts(ans);
	}
    return 0;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏calmound

Remove Nth Node From End of List

问题:删除距离末尾n个距离的结点 分析:先找出距离末尾n个距离的结点其距离开始的距离多少,然后再删除 /** * Definition for singly-...

34150
来自专栏calmound

Search in Rotated Sorted Array

问题:找出某个元素的位置 朴素的暴力方法 class Solution { public: int search(int A[], int n, int...

30850
来自专栏calmound

Remove Duplicates from Sorted Array II

问题:消除数组中重复次数超过三次的多余的数 分析:若ai-1==ai-2若ai也相等,则清楚ai class Solution { public: in...

31150
来自专栏calmound

Swap Nodes in Pairs

问题:交换相邻的两个结点 分析:建立新链表每次插入ret->next后在插入ret,需要在判断下若最后只有一个结点不需要交换,注意每次交换了结点要把尾结点的下一...

31650
来自专栏calmound

Unique Paths

问题:从起点到终点总共有多少条路径 分析:f[x,y]=f[x+1,y]+f[x,y+1],用记忆化搜索就可以解决了 class Solution { publ...

34450
来自专栏calmound

Populating Next Right Pointers in Each Node

问题:将二叉树的所有结点指向他的右边的一个结点 分析:对于每一个结点来说,其操作都是一样的,除了他的左儿子指向右儿子外,其左儿子的全部右后辈均指向其右儿子的全部...

354100
来自专栏calmound

Minimum Depth of Binary Tree

题意:二叉树的最小深度 注意   1.当root为空的时候直接返回0,因为MIN赋值很大,所以如果不单独预判的话会返回MIN         2.判断树的深度应...

36770
来自专栏calmound

Merge Two Sorted Lists

问题:有序合并两个有序链表 分析:归并排序的合并部分 class Solution { public: ListNode *mergeTwoLists(...

37140
来自专栏calmound

Pascal's Triangle II

问题:输出杨辉三角的第n行 class Solution { public: vector<int> getRow(int rowIndex) { ...

29070
来自专栏calmound

Sort Colors

题意:将三种颜色排列,相同的颜色放在一起,依据红绿蓝012的顺序放置 分析:统计红绿蓝分别有多少个,然后重新给数组赋值 class Solution { pub...

36860

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励