回文樹(回文自動機) - 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 |