2016年2月29日 星期一

後綴自動機 (SAM) 圖文教學 (六)

請先參考後綴自動機 (SAM) 圖文教學 (五)

先來看程式碼吧~

code:
#include<cstdio>
#include<cassert>
using namespace std;
struct Node
{
    Node *green,*edge[26];
    int max_len;
    Node(const int _max_len):green(NULL),max_len(_max_len){for(int i=0;i<26;i++)edge[i]=NULL;}
}*ROOT,*LAST;
void Extend(const int c)
{
    Node *cursor=LAST;LAST=new Node((LAST->max_len)+1);
    for(;cursor&&!cursor->edge[c];cursor=cursor->green)cursor->edge[c]=LAST;//添加LAST所有的黑色字串 
    if(!cursor)LAST->green=ROOT;//其實圖上沒有畫綠色邊的點,代表著它的綠色邊是直接指向「代表空串的根結點」
    else
    {
        Node *potential_green=cursor->edge[c];//找出最長的綠色字串(為了要讓LAST代表所有後綴組成的字串集合,要決定綠色邊連到哪),在圖上會走到哪個節點 
        if((potential_green->max_len)==(cursor->max_len+1))LAST->green=potential_green;//剛剛好potential_green代表的字串全部都是LAST的後綴,可以直接利用綠色邊連到potential_green,添加LAST所有的綠色字串 
        else
        {
            assert((potential_green->max_len)>(cursor->max_len+1));//potential_green代表的字串集合中有些不是LAST的後綴
            Node *wish=new Node((cursor->max_len)+1);//從potential_green分離出想要的節點,恰好代表LAST所有的綠色字串 
            for(;cursor&&cursor->edge[c]==potential_green;cursor=cursor->green)cursor->edge[c]=wish;//添加wish所有的黑色字串,同時可能搶走部分potential_green代表的字串集合 
            for(int i=0;i<26;i++)wish->edge[i]=potential_green->edge[i];//讓wish接管原本potential_green黑色邊的功能(防止potential_green下游的節點代表的字串集合中的一些黑色字串,因為potential_green丟掉一些黑色字串而遺失)
wish->green=potential_green->green;//利用綠色邊添加wish所有的綠色字串 
potential_green->green=wish;//利用綠色邊修復potential_green代表的字串集合 
            LAST->green=wish;//利用綠色邊添加LAST所有的綠色字串 
        }
    }
}
char S[10000001],A[10000001];
int N;
int main()
{
    scanf("%d%s",&N,S);
    ROOT=LAST=new Node(0);//SAM的根結點代表空串,max_len當然是0 
    for(int i=0;S[i];i++)Extend(S[i]-'a');
    while(N--)
    {
        scanf("%s",A);
        Node *cursor=ROOT;
        bool ans=true;
        for(int i=0;A[i];i++)
        {
            cursor=cursor->edge[A[i]-'a'];
            if(!cursor){ans=false;break;}//圖上沒有路可以走了,A不是S的子字串 
        }
        puts(ans?"Yes":"No");
    }
    return 0;
}

輸入格式:整數$N$和字串$S$,接下來$N$個字串$A_{i}$ ($A_{i}$代表第$i$個$A$)

這個程式可以先針對$S$建圖,然後$O(\left|A_{i}\right|)$回答每一個$A_{i}$是否為$S$的子字串
是的話輸出$"yes"$,不是的話輸出$"no"$

程式碼裡面已經有滿滿的註解,變數名稱也取得很長,應該可以滿清楚的對應到定義,這裡就不再多做解釋啦~(不負責任?不,因為程式碼講得比純文字敘述清楚太多啦www)
再用紙筆模擬一遍,並且實際編譯程式去跑跑看
確認和之前動手畫的過程是一模一樣的

然後,我們來看看時間複雜度如何吧~
可以發現,最主要的疑點還是void Extend(const int c)裡面的那兩個$while$迴圈

轉換成圖上的情形,就是從上一個節點沿著綠色邊往回走的情況
可以發現,往回走到哪裡,新節點的綠色邊就會指到那個地方沿著對應字母的黑色邊走到的節點
似乎意味著下次再插入一個字母時可以少走多少條綠色邊
可是下次就是從不同的點開始沿著不同的綠色邊往回走惹......

我們必須搞清楚,到底會少走,還是多走......

從$max\_len$下手吧
可以發現:
每沿著綠色邊走一步,$max\_len$一定會嚴格遞減
每沿著黑色邊走一步,$max\_len$一定會嚴格增加$1$

所以,每次插入新字母,$max\_len$嚴格增加$1$,頂多讓整個建圖過程走綠色邊的次數總和多$1$嘛
覺得疑惑?
因為,如果上一次沿著綠色邊最後走到的點,它的$max\_len=x$,那麼這一次沿著綠色邊走一步到達的點,它的$max\_len$就是恰好$=x+1$
還是覺得疑惑?
手動模擬一次看看吧~XD

所以......建立$S$的後綴自動機 ($SAM$) 的時間複雜度均攤是......$O(\left|S\right|)$?!!
太神奇啦!

咦?上一篇不是說這裡要講邊的空間複雜度嗎?
不用擔心啦~
邊的空間複雜度$\leq$建邊的時間複雜度$\leq$建完整個後綴自動機 ($SAM$) 的時間複雜度$=O(\left|S\right|)$

因此邊的空間複雜度自然就$\leq O(\left|S\right|)$啦~~~

其實,有些擁有可愛名字的東西,是有個專有名詞來稱呼的
以後的題解將一律以正式名稱為主
但現階段還是建議用這些可愛的名字來進行思考,以幫助理解

關於一些專有名詞的真相:
節點$\rightarrow$狀態
沿著黑色邊走$\rightarrow$狀態轉移
沒有邊可以走了$\rightarrow$狀態轉移失敗
神奇的綠色邊$\rightarrow$失配邊 (或稱失配函數、失敗指針)


全系列後綴自動機 ($SAM$) 圖文教學
到~此~結~束~!

慶祝一下吧XDD
  
p.s.如果想要背一堆定義+57頁PPT,請左轉陈立杰的演講稿,就不送啦~

5 則留言:

  1. wish->green=potential_green->green;
    这一行中,为什么potential_green的所有绿色字串都可以添加呢?

    回覆刪除
    回覆
    1. 抱歉晚回,最近春節有點忙......

      for(;cursor&&cursor->edge[c]==potential_green;cursor=cursor->green)cursor->edge[c]=wish;
      這一行程式碼中我們已經把potential_green的黑色字串「切出下半部」直接給了wish (然後potential_green就會失去這些黑色字串,所以之後會將potential_green受損的下半部直接以綠色字串的形式替換掉,方法是將綠色邊改連到wish,畢竟最後全部弄好後wish所代表的的字串集合就是它之前被搶走的下半部嘛),但是這只有弄好wish的黑色字串部分。至於為甚麼wish的綠色字串可以直接沿用potential_green的......畢竟我們希望wish代表potential_green的特定下半部嘛,而且這個下半部會包含一部分的黑色字串,而所有的綠色字串都會在黑色字串下面,所以wish的綠色字串就等於potential_green之前的綠色字串囉~
      希望有回答到您的問題~

      刪除
  2. code換個行吧
    註解也可以寫在該行的前面一行
    這樣好難讀ˊˋ

    回覆刪除
    回覆
    1. 之前用來high light的網站掛了所以改code可能有點困難耶抱歉......
      或許可以先把code複製到C++編輯器上再改成您喜歡的樣子?

      刪除

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原