URAL1960 Palindromes and Super Abilities

After solving seven problems on Timus Online Judge with a word “palindrome” in the problem name, Misha has got an unusual ability. Now, when he reads a word, he can mentally count the number of unique nonempty substrings of this word that are palindromes.

Dima wants to test Misha’s new ability. He adds letters s ₁, ..., s _n to a word, letter by letter, and after every letter asks Misha, how many different nonempty palindromes current word contains as substrings. Which n numbers will Misha say, if he will never be wrong?

Input

The only line of input contains the string s ₁... s _n, where s _i are small English letters (1 ≤ n ≤ 10 ⁵).

Output

Output n numbers separated by whitespaces, i-th of these numbers must be the number of different nonempty substrings of prefix s ₁... s _i that are palindromes.

Example

input	output
aba	1 2 3

按顺序每次添加一个字符，求当前本质不同的回文串的数量

回文自动机

刚开始没意识到“本质不同”，加了个统计出现次数……

 1 /*by SilverN*/
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #include<vector>
 8 using namespace std;
 9 const int mxn=102100;
10 int read(){
11     int x=0,f=1;char ch=getchar();
12     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
13     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
14     return x*f;
15 }
16 char s[mxn];
17 struct Pam{
18     int t[mxn][27];
19     int l[mxn],sz[mxn],fa[mxn];
20     int res[mxn];
21     int S,cnt,last;
22     void init(){S=cnt=last=fa[0]=fa[1]=1;l[1]=-1;return;}
23     void add(int c,int n){
24         int p=last;
25         while(s[n-l[p]-1]!=s[n])p=fa[p];
26         if(!t[p][c]){
27             int np=++cnt;l[np]=l[p]+2;
28             int k=fa[p];
29             while(s[n-l[k]-1]!=s[n])k=fa[k];
30             fa[np]=t[k][c];//fail指针
31             t[p][c]=np;
32         }
33         last=t[p][c];
34         sz[last]++;//统计出现次数 
35     }
36     void solve(){
37         printf("%d ",cnt-1);
38 /*
39         memset(res,0,sizeof res);
40         int ans=0;
41         for(int i=cnt;i;i--){
42             res[i]+=sz[i];
43             res[fa[i]]+=res[i];
44             ans+=res[i];
45         }
46         printf("%d ",ans);*/
47         return;
48     }
49 }hw;
50 int main(){
51     int i,j;
52     scanf("%s",s+1);
53     int len=strlen(s+1);
54     hw.init();
55     for(i=1;i<=len;i++){
56         hw.add(s[i]-'a',i);
57         hw.solve();
58     }
59     return 0;
60 }