回文树(回文自动机) - URAL 1960 Palindromes and Super Abilities http://acm.timus.ru/problem.aspx?space=1&num=1960

  Palindromes and Super Abilities

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

Mean: 

给你一个长度为n的字符串S，输出S的各个前缀中回文串的数量。

analyse:

回文树(回文自动机)的模板题。

由于回文自动机中的p是一个计数器，也相当于一个指针，记录的是当前插入字符C后回文树中有多少个节点。

那么我们只需要一路插，一路输出p-2就行。

p-2是因为一开始回文树中就有两个节点。这是两个根节点，分别是长度为偶数和奇数的回文串的根节点。

Time complexity: O(N)

Source code: 

/*

* this code is made by crazyacking

* Verdict: Accepted

* Submission Date: 2015-08-17-14.58

* Time: 0MS

* Memory: 137KB

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#define  LL long long

#define  ULL unsigned long long

using namespace std;

const int MAXN = 100005 ;

const int N = 26 ;

char s[MAXN];

namespace Palindromic_Tree

{

     int next[MAXN][N] ;//next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成

     int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点

     int cnt[MAXN] ;

     int num[MAXN] ;

     int len[MAXN] ;//len[i]表示节点i表示的回文串的长度

     int S[MAXN] ;//存放添加的字符

     int last ;//指向上一个字符所在的节点，方便下一次add

     int n ;//字符数组指针

     int p ;//节点指针

     int newnode(int l)     //新建节点

     {

           for(int i = 0 ; i < N ; ++ i) next[p][i] = 0 ;

           cnt[p] = 0 ;

           num[p] = 0 ;

           len[p] = l ;

           return p ++ ;

     }

     void init()   //初始化

           p = 0 ;

           newnode(0) ;

           newnode(-1) ;

           last = 0 ;

           n = 0 ;

           S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判

           fail[0] = 1 ;

     int get_fail(int x)     //和KMP一样，失配后找一个尽量最长的

           while(S[n - len[x] - 1] != S[n]) x = fail[x] ;

           return x ;

     void add(int c)

           c -= 'a' ;

           S[++ n] = c ;

           int cur = get_fail(last) ;   //通过上一个回文串找这个回文串的匹配位置

           if(!next[cur][c])     //如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串

           {

                 int now = newnode(len[cur] + 2) ;   //新建节点

                 fail[now] = next[get_fail(fail[cur])][c] ;   //和AC自动机一样建立fail指针，以便失配后跳转

                 next[cur][c] = now ;

                 num[now] = num[fail[now]] + 1 ;

           }

           last = next[cur][c] ;

           cnt[last] ++ ;

     void Count()

           for(int i = p - 1 ; i >= 0 ; -- i) cnt[fail[i]] += cnt[i] ;

           //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！

} ;

using namespace Palindromic_Tree;

int main()

     ios_base::sync_with_stdio(false);

     cin.tie(0);

     while(~scanf("%s",s))

           init();

           for(int i=0;s[i];++i)

                 add(s[i]);

                 printf(i==0?"%d":" %d",p-2);

           puts("");

//            Count();

     return 0;

}

代码2：

* Submission Date: 2015-08-17-16.51

const int MAXN = 100010;

struct node

     int next[26];

     int len;

     int sufflink;

     int num;

};

int len;

node tree[MAXN];

int num; // node 1 - root with len -1, node 2 - root with len 0

int suff; // max suffix palindrome

long long ans;

bool addLetter(int pos)

     int cur = suff, curlen = 0;

     int let = s[pos] - 'a';

     while(true)

           curlen = tree[cur].len;

           if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos]) break;

           cur = tree[cur].sufflink;

     if(tree[cur].next[let])

           suff = tree[cur].next[let];

           return false;

     } suff = ++num;

     tree[num].len = tree[cur].len + 2;

     tree[cur].next[let] = num;

     if(tree[num].len == 1)

           tree[num].sufflink = 2;

           tree[num].num = 1;

           return true;

           if(pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])

                 tree[num].sufflink = tree[cur].next[let];

                 break;

     tree[num].num = 1 + tree[tree[num].sufflink].num;

     return true;

void initTree()

     num = 2; suff = 2;

     tree[1].len = -1; tree[1].sufflink = 1;

     tree[2].len = 0; tree[2].sufflink = 1;

     scanf("%s",s);

     len = strlen(s);

     initTree();

     for(int i = 0; i < len; i++)

           addLetter(i);

           printf(i==0?"%d":" %d",num-2);

//            ans += tree[suff].num;

     putchar(10);

//       cout << ans << endl;

      |  Github |  Facebook  |  Twitter |