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}