後綴自動機 (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，請左轉陈立杰的演講稿，就不送啦～