论如何优雅的处理回文串 - 回文自动机详解
?
寫在前面
最近無意中看到了這個數(shù)據結構，順便也就學習了一下。
而且發(fā)現(xiàn)網上關于這個算法的描述有很多地方是錯的，在這里做了一些更正。
處理字符串的算法很多：
? ? KMP,E-KMP,AC自動機,后綴三兄弟:后綴樹、后綴數(shù)組、后綴自動機,Trie樹、Trie圖,符串hash...
但以上數(shù)據結構在處理回文串上還是稍有欠缺，用這些來處理回文顯得太小題大做。
于是有了Manacher算法，代碼短、容易理解、時間O(n)、無需考慮奇偶回文情況，很完美的算法！
當然這篇博客的重點不在Manacher算法，有關Manacher算法請點擊這里！
Manacher算法可以在O(n)時間內處理出S串每個位置的最長回文串，但如果要統(tǒng)計S串中有多少回文串，
或者S串的所有子串的回文串的個數(shù),這時就要用到一種和Manacher一樣優(yōu)雅的數(shù)據結構：回文自動機。
What ?Is ?Palindromic auto-machine?
回文自動機，又叫回文樹，是由俄羅斯人?MikhailRubinchik于2014年夏發(fā)明的，參看鏈接。
這是一種比較新的數(shù)據結構，在原文中已有詳細介紹與代碼實現(xiàn)。
回文樹其實不是嚴格的樹形結構，因為它有是兩棵樹，分別是偶數(shù)長度的回文樹和奇數(shù)長度的回文樹，樹中每個節(jié)點代表一個回文串。
為了方便，第一棵樹的根是一個長度為0的串，第二棵就是為-1的串，不要感到奇怪，就是-1。
可以證明，最多只有n個結點（n是串的長度）。這個可以用Manacher算法來證明。
如果某結點代表的是串ccabacc，那么它的父親代表的串就是去掉前后兩個字符cabac。
每個點還有一個fail指針，表示這個串的后綴中最長的回文串，比如babab的fail指向bab，bab的指向b。
方法的思想和KMP，AC自動機很類似，如果你理解了KMP與AC自動機，那么這個算法基本可以一看就懂。
數(shù)據說明
- len[i]:節(jié)點i的回文串的長度
- next[i][c]：節(jié)點i的回文串在兩邊添加字符c以后變成的回文串的編號(和字典樹的next指針類似)
- fail[i]：類似于AC自動機的fail指針，指向失配后需要跳轉到的節(jié)點
- cnt[i]：節(jié)點i表示的回文串在S中出現(xiàn)的次數(shù)（建樹時求出的不是完全的，count()加上子節(jié)點以后才是正確的）
- num[i]：以節(jié)點i回文串的末尾字符結尾的但不包含本條路徑上的回文串的數(shù)目。(也就是fail指針路徑的深度)
- last：指向最新添加的回文結點
- S[i]表示第i次添加的字符
- p表示添加的節(jié)點個數(shù)
How To Build Palindromic auto-machine?
假設現(xiàn)在我們有串S='abbaabba'。
首先我們添加第一個字符'a'，S[++ n] = 'a'，然后判斷此時S[n-len[last]-1]是否等于S[n]
即上一個串-1的位置和新添加的位置是否相同，相同則說明構成回文，否則，last=fail[last]。
此時last=0，我們發(fā)現(xiàn)S[1-0-1]!=S[1]，所以last=fail[last]=1，
然后我們發(fā)現(xiàn)S[1-(-1)-1]==S[1]（即自己等于自己，所以我們讓len[1]等于-1可以讓這一步更加方便）。
令cur等于此時的last（即cur=last=1），判斷此時next[cur]['a']是否已經有后繼，
如果next[cur]['a']沒有后繼，我們就進行如下的步驟：
新建節(jié)點（節(jié)點數(shù)p++，且之后p=3），并讓now等于新節(jié)點的編號（now=2），
則len[now]=len[cur]+2（每一個回文串的長度總是在其最長子回文串的基礎上在兩邊加上兩個相同的字符構成的，所以是+2，
同時體現(xiàn)出我們讓len[1]=-1的優(yōu)勢，一個字符自成一個奇回文串時回文串的長度為(-1)+2=1）。
然后我們讓fail[now]=next[get_fail ( fail[cur] )]['a']，即得到fail[now]（此時為fail[2] = 0），
其中的get_fail函數(shù)就是讓找到第一個使得S[n-len[last]-1]==S[n]的last。然后next[cur]['a'] = now。
當上面步驟完成后我們讓last = next[cur][c]（不管next[cur]['a']是否有后繼），然后cnt[last] ++。
此時回文樹為下圖狀態(tài)：
現(xiàn)在我們添加第二個字符字符'b'到回文樹中：
繼續(xù)添加第三個字符'b'到回文樹中：
繼續(xù)添加第四個字符'a'到回文樹中：
?繼續(xù)添加第五個字符'a'到回文樹中：
?繼續(xù)添加第六個字符'b'到回文樹中：
?繼續(xù)添加第七個字符'b'到回文樹中：
?繼續(xù)添加第八個字符'a'到回文樹中：
?到此，串S已經完全插入到回文樹中了，現(xiàn)在所有的數(shù)據如下：
?
?
?
?
然后我們將節(jié)點x在fail指針樹中將自己的cnt累加給父親，從葉子開始倒著加，最后就能得到串S中出現(xiàn)的每一個本質不同回文串的個數(shù)。
構造回文樹需要的空間復雜度為O（N*字符集大小），時間復雜度為O（N*log（字符集大小）），這個時間復雜度比較神奇。如果空間需求太大，可以改成鄰接表的形式存儲，不過相應的要犧牲一些時間。
The Use Of Palindromic auto-machine
some problem
Template
/* * this code is made by crazyacking * Verdict: Accepted * Submission Date: 2015-08-19-21.48 * 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]; struct Palindromic_Tree {int next[MAXN][N] ;//next指針，next指針和字典樹類似，指向的串為當前串兩端加上同一個字符構成int fail[MAXN] ;//fail指針，失配后跳轉到fail指針指向的節(jié)點int cnt[MAXN] ;int num[MAXN] ; // 當前節(jié)點通過fail指針到達0節(jié)點或1節(jié)點的步數(shù)(fail指針的深度)int len[MAXN] ;//len[i]表示節(jié)點i表示的回文串的長度int S[MAXN] ;//存放添加的字符int last ;//指向上一個字符所在的節(jié)點，方便下一次addint n ;//字符數(shù)組指針int p ;//節(jié)點指針int newnode(int l) //新建節(jié)點 {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,int pos){printf("%d:",p);c -= 'a';S[++ n] = c ;int cur = get_fail(last) ; //通過上一個回文串找這個回文串的匹配位置printf("%d ",cur);if(!next[cur][c]) //如果這個回文串沒有出現(xiàn)過，說明出現(xiàn)了一個新的本質不同的回文串 {int now = newnode(len[cur] + 2) ; //新建節(jié)點fail[now] = next[get_fail(fail[cur])][c] ; //和AC自動機一樣建立fail指針，以便失配后跳轉next[cur][c] = now ;num[now] = num[fail[now]] + 1 ;for(int i=pos-len[now]+1; i<=pos; ++i) printf("%c",s[i]);} last = next[cur][c] ;cnt[last] ++ ;putchar(10);}void count(){for(int i = p - 1 ; i >= 0 ; -- i) cnt[fail[i]] += cnt[i] ;//父親累加兒子的cnt，因為如果fail[v]=u，則u一定是v的子回文串！ } } run; int main() {scanf("%s",&s);int n=strlen(s);run.init();for(int i=0; i<n; i++) run.add(s[i],i);run.count();return 0; }?
與50位技術專家面對面20年技術見證，附贈技術全景圖總結
以上是生活随笔為你收集整理的论如何优雅的处理回文串 - 回文自动机详解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： JS三教九流系列-require.js-
- 下一篇： Cordova实战培训