??? 在回答什么是suffix auto machine前我們需要先知道什么是auto machine。

??? 什么是自動機？一個FSN（有限狀態(tài)自動機）就是一個具有識別字符串S對于自動機A是true還是false；即當s屬于alpha，判斷trans（state，ch）是否等于end；

??? 同時令trans(state,str)表示當前狀態(tài)是s，在讀入字符串str之后，所到達的狀態(tài)。 ??? 而一個sam就是一個能夠識別字符s所有后綴的自動機。 ??? 我們可以像AC自動機一樣，在trie上建立sam，但顯然對于長度為N的串可能有N^2個結點；能不能優(yōu)化呢？ ??? 我們可以先空想一個假設存在一個叫最簡狀態(tài)后綴機的東西，在還沒有構造出這個東西前我們可以先看看它會有什么性質。 ??? 設有一母串S，它的所有后綴集合為suf，設從a開始的后綴為suffix（a），定義st（str）=trans（init，str），reg（st（a））為st（a）能識別出的字符串集； ??? 性質一：若串s不屬于suf則st（s）=null； ??? 性質二：若串s屬于suf則st（s）！=null； ??? 推論1：x能被自動機識別當且僅當x屬于suf； ??? 推論2:st（a）能識別x當且僅當ax屬于suf；
??? 推論3:如果a在s的范圍為【l，r）則st（a）能識別S從r開始的后綴； ??? 推論4:如果a在s的范圍集合為【L1，R1），【L2，R2），【L3，R3）。。。【Ln，Rn），則st（a）能識別以R1，R2，R3.。。Rn開始的后綴,設right（a)={R1,R2,R3...Rn}; ??? 性質三：若對兩個串a(chǎn)，b屬于fac，且right（a）=right（b），則st（a）=st（b），所以狀態(tài)s可以簡化為所有right集合為right（s）的串的公共母串； ??? 性質四：若r屬于right（s），且已知子串長度len，則該子串為S【r-len，r），且顯然長度len的可選范圍為一個區(qū)間，則可令s的區(qū)間為【min（s），max（s）】； ??? 這時最簡狀態(tài)后綴機的線性性就顯然了； ??? 而我們可以用簡化后的right集合構建一顆樹，不妨取名parent，則顯然max（fa（s））=min（s）-1； ??? 顯然以轉移方式建樹的邊也不會超過o（n）； ??? 由于父親的right集是它的后代的所有right集的并集，所以我們可以用樹的dfs序排列建樹； ??? 下面是kuangbin的后綴自動機板子； ????

structSAM_Node
{

SAM_Node*fa,*next[CHAR];intlen;
intid,pos;
SAM_Node(){}

SAM_Node(int_len){

fa= 0;
len= _len;memset(next,0,sizeof(next));

}};

SAM_NodeSAM_node[MAXN*2], *SAM_root, *SAM_last;intSAM_size;
SAM_Node*newSAM_Node(intlen)
{

SAM_node[SAM_size] =SAM_Node(len);SAM_node[SAM_size].id= SAM_size;return&SAM_node[SAM_size++];

}
SAM_Node*newSAM_Node(SAM_Node*p){

SAM_node[SAM_size] = *p;SAM_node[SAM_size].id= SAM_size;return&SAM_node[SAM_size++];

}
voidSAM_init(){

SAM_size = 0;
SAM_root = SAM_last = newSAM_Node(0);SAM_node[0].pos= 0;

}
voidSAM_add(intx,intlen){

SAM_Node*p = SAM_last, *np = newSAM_Node(p->len+1);np->pos= len;
SAM_last = np;for(;p && !p->next[x];p = p->fa)p->next[x] = np;

if(!p){

np->fa= SAM_root;

return;}

SAM_Node*q = p->next[x];if(q->len== p->len+ 1){

np->fa= q;

return;}

SAM_Node*nq = newSAM_Node(q);nq->len= p->len+ 1;
q->fa= nq;
np->fa= nq;

for(;p && p->next[x] == q;p = p->fa)p->next[x] = nq;

}
voidSAM_build(char*s){

SAM_init();
intlen =strlen(s);for(inti = 0;i < len;i++)

SAM_add(s[i] -'a',i+1);

}

//加入串后進行拓撲排序。charstr[MAXN];
inttopocnt[MAXN];SAM_Node*topsam[MAXN*2];

intn =strlen(str);SAM_build(str);memset(topocnt,0,sizeof(topocnt));for(inti = 0;i < SAM_size;i++)

topocnt[SAM_node[i].len]++;for(inti = 1;i <= n;i++)

topocnt[i] += topocnt[i-1];for(inti = 0;i < SAM_size;i++)

topsam[--topocnt[SAM_node[i].len]] = &SAM_node[i];

???
? 好了。。。拜拜～～
???
???

總結

以上是生活随笔為你收集整理的suffix automachine-陈立杰讲稿学习笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。