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

題目大意：

有一串項鍊由於線繩脆弱，可能會在最重與最輕的珠子的中間因為重力關係而導致繩線裂開，這些珠子的權重分別用英文字母表示，由於這些英文字母是循環的，給你一組字串試問怎麼樣找出此字串字典序最小的循環字串。

循環字串：假如字串有 “abc”，那則會 abcabcabc… 不斷循環下去，但總長度必定為原本字串長度，類似於項鍊。

分析：

這題使用 Suffix Automation 做最小循環移位(Lexicographically minimum string rotation)是不錯的選擇，Suffix Automation 是甚麼？那你可以看看演算法知識 - Suffix Automaton 後綴自動機，裡面有對於 Suffix Automation 做出還不賴的說明，也可以利用他的參考連結去找到更適合你的說明方式。

QUESTION: 最小循環移位(Lexicographically minimum string rotation) 是甚麼？

給你一組字串，找出字典序最小的循環字串，沒錯，就是這題的題目，非常純粹的模板題。

要怎麼解開呢？

其實容易想到，只需要將原本的字串複製一次給原本的字串，即string += string，透過從起始點一路跟著當下可以走的最小字典序節點走，走到原先字串的長度，在k-string.length()+1，就是最小循環移位了。

QUESTION A: 為甚麼只要原本的字串複製一次給原本的字串呢？

由於第一次的字串長度結束位置 + 字串長度(即第二次循環) < 連續三次循環長度，就算從最後一個字元開始循環也不會大於三次循環，即可證明我們不需要第三次循環，只要循環一次就好。

簡單的程式碼說明

//st 是 sam、now 是還要再找幾次，一開始為原本字串長度
while(now--){
    for(auto it : st[u].next){ //跟著字典續追蹤
        u = it.second ;
        break ; //找到了就往下個節點移動，類似於 DFS
    }
}
cout << st[u].len - len + 1 << '\n' ; 
//找到當下的節點後，找出它的長度並且扣掉原始長度並加一即是答案

參考連結

uva 719 - Glass Beads(最小表示法 | 后缀自动机)
后缀自动机 (SAM)
演算法知識 - Suffix Automaton 後綴自動機

心得

其實學會了 SAM 之後，發現這個應用沒有難度欸XD，SAM 太讚了，SAM 不知道是哪個優秀的演算法大神發明的，真的非常棒，只是我不爭氣了解的不夠透徹、不夠多，我要繼續努力學習演算法，使我變強也能夠獨當一面！也還要複習英文，不然題目可能都看不懂，嗚嗚。

題目程式碼

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

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

於是這裡就補述一些題目給的資料範圍限制與標頭檔了。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAl
#define N 10010
#define SAMN N*10
using namespace std;
int sz , last ;
struct state{
    int len , link ;
    map<char,int> next ;
}st[SAMN];

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

void sam_extend(char c ){
    int cur = sz++ ;
    st[cur].next.clear() ;
    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 ;
}


int main()
{
#ifdef LOCAl
    freopen("in1.txt" , "r" , stdin );
#endif // LOCAl
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n , len;
    string strA ;
    cin >> n ;
    while(n--){
        cin >> strA ;
        len = strA.length() ;
        strA += strA ;
        sam_init() ;
        for(int i = 0 ; i < strA.length() ; i++) sam_extend(strA[i]);

        int u = 0 , now = len  ;
        while(now--){
            for(auto it : st[u].next){
                u = it.second ;
                break ;
            }
        }
        cout << st[u].len - len + 1 << '\n' ;
    }
    return 0;
}