# URAL 2040 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

```#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;
}
{
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++)
{
ans[i]='0';
else
ans[i]='1';
}
ans[i]='\0';
puts(ans);
}
return 0;
}```

0 条评论

34150

30850

31150

31650

34450

354100

36770

37140

29070

36860