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

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

回文自动机

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

 /*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<vector>

 using namespace std;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 char s[mxn];

 struct Pam{

     int t[mxn][];

     int l[mxn],sz[mxn],fa[mxn];

     int res[mxn];

     int S,cnt,last;

     void init(){S=cnt=last=fa[]=fa[]=;l[]=-;return;}

     void add(int c,int n){

         int p=last;

         while(s[n-l[p]-]!=s[n])p=fa[p];

         if(!t[p][c]){

             int np=++cnt;l[np]=l[p]+;

             int k=fa[p];

             while(s[n-l[k]-]!=s[n])k=fa[k];

             fa[np]=t[k][c];//fail指针

             t[p][c]=np;

         }

         last=t[p][c];

         sz[last]++;//统计出现次数

     }

     void solve(){

         printf("%d ",cnt-);

 /*

         memset(res,0,sizeof res);

         int ans=0;

         for(int i=cnt;i;i--){

             res[i]+=sz[i];

             res[fa[i]]+=res[i];

             ans+=res[i];

         }

         printf("%d ",ans);*/

         return;

     }

 }hw;

 int main(){

     int i,j;

     scanf("%s",s+);

     int len=strlen(s+);

     hw.init();

     for(i=;i<=len;i++){

         hw.add(s[i]-'a',i);

         hw.solve();

     }

     return ;

 }

巴特西

URAL1960 Palindromes and Super Abilities

最新文章

热门文章