ural 1960. Palindromes and Super Abilities (回文自动机,统计本质不同的回文串个数)

http://acm.timus.ru/problem.aspx?space=1&num=1960

题意:

给一个字符串S,依次输出字符串S的所有前缀中,本质不同的回文串个数。

思路:

考虑构建PAM是一个增量算法...所以一边构建一边输出答案就好了。。。

某一时刻本质不同的回文串个数就是sz-1 (标号是从0..sz,一共sz+1个,减去2个根,所以是sz-1)

/* ***********************************************
Author :111qqz
Created Time :2017年11月14日 星期二 01时01分03秒
File Name :2565.cpp
************************************************ */
 1#include <bits/stdc++.h>
 2#define PB push_back
 3#define fst first
 4#define sec second
 5#define lson l,m,rt<<1
 6#define rson m+1,r,rt<<1|1
 7#define ms(a,x) memset(a,x,sizeof(a))
 8typedef long long LL;
 9#define pi pair < int ,int >
10#define MP make_pair
 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=1E5+7;
 7struct PAM
 8{
 9    int fail,cnt,len;
10    int nxt[26];
11}st[N];
12char S[N],RS[N];
13int n,now,sz;
14void pam_init()
15{
16    ms(st,0);
17    st[0].fail = st[1].fail = 1;
18    st[1].len = -1;
19    sz = 1;
20}
21void extend(int c,int pos)  
22{
23    int p = now;
24    while (S[pos-st[p].len-1]!=S[pos]) p = st[p].fail;
25    if (!st[p].nxt[c]){
26    int np=++sz,q=st[p].fail;
27    st[np].len=st[p].len+2;
28    while (S[pos-st[q].len-1]!=S[pos]) q=st[q].fail;
29    st[np].fail=st[q].nxt[c];
30    st[p].nxt[c] = np;
31    }
32    now=st[p].nxt[c];
33    st[now].cnt++;
34}
35int main()
36{
37    #ifndef  ONLINE_JUDGE 
38//  freopen("./in.txt","r",stdin);
39  #endif 
40    scanf("%s",S);
41    pam_init();
42    n = strlen(S);
43    vector <int>ans;
44    for ( int i = 0 ; i < n; i++) extend(S[i]-'a',i),ans.PB(sz-1);
45    int siz = ans.size();
46    for ( int i = 0 ; i < siz ; i++) printf("%d%c",ans[i],i==siz-1?'\n':' ');
47  #ifndef ONLINE_JUDGE  
48  fclose(stdin);
49  #endif
50    return 0;
51}