演算法知識 - Suffix Automaton 後綴自動機

Suffix Automaton 介紹

Suffix Automaton，簡稱 SAM，(以下內文都簡稱 SAM)，是一個能解決許多字串特定問題的資料結構。

只要關於這兩個字串問題都可以使用 \(O(n)\) 時間複雜度解決：

• 在另一個字串中查詢另一個字串的所有出現位置
• 計算此字串中裡面有多少不同的子字串

簡單來說 SAM 可以理解成字串壓縮，一個 SAM 最多只會有 \(2n-1\) 個節點與 \(3n-4\) 個轉移邊。

建立 SAM 的時間複雜度為 \(O(n)\)

此文章跳開蠻多理論與證明，如果想要知道可再從下方參考連結點選即可

Suffix Automaton 原理

需要用到 struct，此 struct 需要 len , link , next，這些的意義為：

• len 目前的最長長度
• link 為當前子字串中第一個最長後綴結束位置
• next 連結其他的點的邊，方向是 ->

Suffix Automaton 圖示說明：

我們假設此字串為 “aabbabd”，下方圖片的線為：

• link 為綠色線
• next 為藍色線
• len 從起點到終點的最長長度

我們感謝一下畫這張圖的大神，不得不說話的超棒

重大的三個特性

• 跟著藍色線走到終點時會是必定是 “aabbabd” 的後綴
• 跟著藍色線走到任意點必定會是此字串的子字串
• 發明這個的演算法大師太強了，跟神一般的存在

好啦，其實是兩個，但是沒有第三個前面兩個都不會成立XD
根據這張圖大概就能夠理解後綴自動機在說甚麼了，不懂別打我~~。

程式碼實現與說明

程式碼實現與說明分成三大部分，建構、初始化、SAM 擴增長度。

建構

一個 SAM 必須要有從出發點到此的最長長度，離起點最近的位置、與連結其他點的邊。

#define SAMN N*10 
// N 為字串最長長度
int sz , last ; // 到 SAM 初始化說明

struct state{
    int len , link ; // len = 最長長度 , link = 當前子字串中第一個最長後綴結束位置 

    map<char,int> next ;
}st[SAMN];

初始化

先給予一開始的起點，由於起點(當前狀態為空字串)並不會有後綴於是我們 link 直接設為 -1，且長度(len)為 0。

void sam_init(){
    sz = 0 ;
    st[0].len = 0 ;
    st[0].link = -1 ;
    st[0].next.clear();
    sz++ ;
    last = 0 ;
}

SAM 增加長度

這裡就比較複雜了，應該是說超級複雜，我在程式中一行一行註解相信會更容易許多。

請讀者特別注意，「子字串」跟「字串」要仔細分別，不要忽略會很嚴重

void sam_extend(char c ){ //char c 要擴增的字元
    int cur = sz++ ; //sz++ 增加 sam array 長度 , cur 為當前的 sam 節點
    st[cur].next.clear() ; //先把當前的 sam 連接點狀態移除
    st[cur].len = st[last].len+1 ; //為前一個 sam 節點 len +1 表示其長度
    int p = last ; // p = 查詢當前字串的「所有子字串」與新增加 c 後的字串是否有共同後綴，
    //將跑到他們有共同後綴的「前一個位置」
    //注意：這裡的共同後綴只要有一個字元是就可以是共同後綴
    //舉例："abca" and "abcab" 中的 'b' 就是共同後綴

    while(p != -1 && !st[p].next.count(c)){ // p = -1 表示已經到起點，
        // !st[p].next.count(c) 則是詢問增加此字元後是否會有共同後綴的情形，
        // 如果有則需要額外處理
        st[p].next[c] = cur ; // 將前面的點與現在的 sam 節點做連結
        p = st[p].link ; // 由於現在的字元並沒有和前面的子字串有共同後綴，
        // 於是他們的 link 就向上追蹤
        // 如果有則 st[p].next.count(c) == TRUE 不符合迴圈要求
    }
    if(p == -1){ 
        // p = -1 表示沒有共同後綴且此字元在當前字串中從沒出現過，
        //才回到了起始點，所以將 link 設置為 0 
        st[cur].link = 0 ; 
    }
    else{
        int q = st[p].next[c] ; // q 為他們共同後綴的位置
        if(st[p].len + 1 == st[q].len){ 
            //如果 st[p].len + 1 == st[q].len 表示「不同位置但相同字元」的共同後綴長度大於一
            //只需要直接將當前的 sam[cur].link 設定成 q 也就是共同後綴的位置 
            st[cur].link = q ;
        }
        else{ // 如果不同位置但相同字元的共同後綴如果等於一，則需要連創建新的 sam 節點，
            // 建立以 c + 字串前一個字元的後綴(前一個並不包括我們現在新增的 c)，
            // 並同時放棄另一個不同位置但也是 c 字元的後綴，但要持續存在以保護先前做好的 sam
            int clone = sz++ ; // 創建新節點
            st[clone].len = st[p].len + 1 ; // 表示從共同後綴的前一個位置 +1，
            //用來建立以 c + 字串前一個字元的後綴
            st[clone].next = st[q].next ; //複製 q 的 next，因為前面已經設定好連接的點，
            //但是因為共同後綴不同，後面還需要一個 while 迴圈進行調整
            st[clone].link = st[q].link ; //將他們 link 先設置相同，
            //之後用 while 迴圈再移動到正確的 link
            while(p != -1 && st[p].next[c] == q){ 
                //p != -1 是不可以讓她更改起始點的位置
                //st[p].next[c] == q 接下來的點是從 clone 繼續擴展而不是原先的 q，
                //所以要將原先連接到 q 的點全部改連接至 clone
                st[p].next[c] = clone ; //更改連接點至 clone
                p = st[p].link ; // 繼續往上層追蹤
            }
            st[q].link = st[cur].link = clone ;
            // 最後則是也要把 q and cur 的 link 改到 clone，
            // 原因則是因為接下來的點是從 clone 繼續擴展而不是原先的 q
        }
    }
    last = cur ; //準備下一次的擴展
}

想必蠻多讀者看完還是不知道這到底是甚麼鬼對不對？沒關係，我自己在寫這個註解花了三小時，我自己都不太知道怎麼說明比較好，這有點太抽象了

我在這邊強烈希望讀者可以根據我的 Exercise 練習，就可以知道不容易寫以及其抽象的原因。

EXERCISE A: 劃出 SAM 的圖，字串是 “abccba”

EXERCISE B: 根據 Exercise A 甚麼時後會用到 if(st[p].len + 1 == st[q].len) 的 else 情況？

在現在新增字元與現在的 SAM 圖中字元一樣但後綴不大於一時，新增 clone 點，並放棄原本的 q 點，但必須保留以保證先前的 SAM 狀態正確。

SAM 應用

我在學習此演算法的過程中如果有題目讓我應用到此演算法我則收錄在此，連結則是我的詳解如果想要去看題目的就搜尋一下吧！

最小循環移位

• UVa719 - Glass Beads (Suffix Automaton 後綴自動機 - 最小循環移位 Lexicographically minimum string rotation)

參考連結

后缀自动机 (SAM)
后缀自动机学习笔记

心得

感覺 SAM 沒有學得很好啊 ಥ⌣ಥ，沒辦法把一個抽象的事物說明的很清楚是我的問題呀，嗚嗚嗚嗚，這次就算有手寫程式碼以後還是有很多的學習盲點沒有意識到，慢慢再看其他教導 SAM 的文章才搞懂了些，SAM 是一個很酷、很強大的資料結構，發明 SAM 的人是一個大神吧。

這一次我不會說學習 SAM 會增加我的思維，因為我在寫完 blog 的感覺並沒有幫助我擴展我的思維，我想是我理解的不夠深或是依我當前的背景知識學習 SAM，會讓我自己不懂優秀的人們背後的學習理論，而導致我可能是用死背的方式得出結論。

雖然我有可能是用死背的方式得出結論，但我也花了一個禮拜在嘗試與思考此問題，我的腦袋沒有辦法好好描述 SAM 的程式碼，但我的腦袋卻告訴我她已經熟悉這個算法，但我無法肯定是不是用背的還是理解的，希望我自己是有理解到但只是我的腦袋還沒辦法用口語述說。

自學很好，但自學常常會遇到很多思考盲點；因為自學比較難有系統地去學習，學習方式是用跳躍的，常常是自己在學習其他觀念時才會想到，對欸！我之前學的哪個演算法就是用這個基礎去延伸的，這樣其實不太好，有點討厭，但我一路以來的學習方法也都是如此，可能也沒有辦法再去讓自己習慣另一種模式，就繼續堅持下去吧！我相信只要我堅持，美好的成果我一定也能品嘗到的！

也謝謝 OI WIKI 與 stevensonson 一個用證明與理論來讓我學習 SAM、優質的 SAM 程式碼讓我對此演算法學習速度更快，另一個則是使用圖加速了我對 SAM 的理解，謝謝二位大神，也還希望 stevensonson 願意讓我用此圖來對未來可能會忘記這演算法的我、其他想學的人進行說明，謝謝！

我也花了七個小時撰寫文章，看得懂跟說得出來真的是兩回事，也許還有人覺得我說的很差，不過我已經盡力解釋。希望可以幫助到各位。

也希望大家想要學習的知識都可以快速學習而成，不要因為自身的環境不足而學習不到。

SAM 無註解程式碼

這裡則放置沒有註解的程式碼，如果讀者想要複製就從這裡進行複製吧！

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct state {
  int len, link;
  std::map<char, int> next;
};
const int MAXLEN = 100000;
state st[MAXLEN * 2];
int sz, last;

void sam_init() {
  st[0].len = 0;
  st[0].link = -1;
  sz++;
  last = 0;
}

void sam_extend(char c) {
  int cur = sz++;
  st[cur].len = st[last].len + 1;
  int p = last;
  while (p != -1 && !st[p].next.count(c)) {
    st[p].next[c] = cur;
    p = st[p].link;
  }
  if (p == -1) {
    st[cur].link = 0;
  } else {
    int q = st[p].next[c];
    if (st[p].len + 1 == st[q].len) {
      st[cur].link = q;
    } else {
      int clone = sz++;
      st[clone].len = st[p].len + 1;
      st[clone].next = st[q].next;
      st[clone].link = st[q].link;
      while (p != -1 && st[p].next[c] == q) {
        st[p].next[c] = clone;
        p = st[p].link;
      }
      st[q].link = st[cur].link = clone;
    }
  }
  last = cur;
}

用紙筆去模擬 SAM

因為只是自己在思考過程中隨手做的筆記，覺得不是對讀者這麼有幫助，因此放在文章最下面。

有時候用想或用看的可能不太能夠懂這演算法，那就用寫的吧！這是大衛我自己學習的手稿，紀錄者我的學習過程。

這裡的舉例是用 “daviddavid”

最後一張則是我自己其他幫助我自己內心釐清的手稿，非常沒用，不要看，我純紀念用