UVa1223 - Editor (Suffix Tree 後綴樹 - 最長重複子字串 Longest Repeated Substring)

題目大意：

有一位優秀的程式設計師想要寫出一個 Editor，他希望你幫他寫出一個功能關於在一個字串中找出最長重複子字串，並輸出總共出現幾次。

分析：

標準的最長重複子字串 Longest Repeated Substring問題，使用 Suffix Tree 是不錯的選擇，如果你不知道 Suffix Tree 是甚麼？那你可以去看看演算法知識 - Suffix Tree 後綴樹 (Using Ukkonen Algorithm)，裡面有對於 Suffix Tree 做出還不賴的說明，也可以利用他的參考連結去找到更適合你的說明方式。

QUESTION A: 最長重複子字串 (Longest Repeated Substring) 是甚麼？

給你一組字串，找出最長的重複子字串，就跟字面上的意思一樣，這題可以算是一個模板題。

那要怎麼解題呢？

其實容易想到，做一次 DFS，由於 Suffix Tree 的特性是只要不是 leaf(葉節點)就表示至少此節點下面有兩個 leaf，透過此特性可以知道重複的特性，再透過 DFS 向下追蹤的特性可以找出 最長重複子字串，再利用此節點下有多少個 leaf，就可以知道重複幾次了！

QUESTION B: 那要怎麼找到最長重複子字串 (Longest Repeated Substring) 開的 index 呢？

簡單，只需要用葉節點的 start 減掉 LRS(最長重複子字串) 長度就可以知道是從哪個 index 開始了！

簡單的程式碼說明

請注意，這題只需要輸出 max_lrs 即可，但我為了 debug 方便因此全部都先寫出來方便除錯。

void lrs_dfs(int r , int len , int repeats ){ //dfs for suffix tree
    for(auto it : tree[r].next){ // 向下追蹤節點
        lrs_dfs(it.second , len + tree[r].edge_length() , tree[r].next.size());
        // len + tree[r].edge_length()  當前最長重複長度
        //  tree[r].next.size() 下面有幾個節點表示至少重複幾次 
    }
    if(tree[r].slink == 0 && len > max_lrs){ 
        //走訪到根節點且當前最長重複長度 > 最長重複子字串 則將當前的資料都換成 LRS 表示
        lrs_repeat = repeats ; // 重複次數
        max_lrs = len ; // 長度
        lrs_index = tree[r].start - len ; // 初始的 index
    }
    return ;
}

參考連結

演算法知識 - Suffix Tree 後綴樹 (Using Ukkonen Algorithm)
UVa11512 - GATTACA (Suffix Tree 後綴樹 - 最長重複子字串 Longest Repeated Substring)

心得

老實講學完了 Suffix Tree 感覺真的很不賴，這題可以馬上解開讓我自己有滿滿的成就感呢XD，希望以後遇到我有學過的題目都可以這樣迅速解開那是最棒的了！也希望我所學的演算法知識都能應用在實務上，這樣一定會讓我更肯定學習演算法是正確也是必要的事情！

總感覺自己把成功視為理所當然，失敗視為禁忌，失敗的心得總是在檢討自己，成功時都在為自己感到自信，感覺有點不太好呢！不過如果這樣可以讓自己進步的話，似乎也不錯嗎？讓我慢慢長大慢慢檢視我自己吧！好像有點用太多驚嘆號了

題目程式碼

其實就是沒有附上說明的程式碼，希望可以幫助到各位，也期望大家想要學習的知識都可以快速學習而成，不要因為自身的環境不足而學習不到。

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define N 5020
using namespace std;
int root , cnt , pos , needSL ,remainder_ ,
    active_node , active_e , active_len ;
string text ;
int oo ;
int max_lrs = 0 , lrs_index = 0 , lrs_repeat = 0 ;

struct node{
    int start , end , slink ;
    map<char,int> next ;

    int edge_length(){
        return min(end,pos+1) - start ;
    }

    void init(int st , int ed = oo){
        start = st ;
        end = ed ;
        slink = 0 ;
        next.clear() ;
    }
}tree[2*N];

char active_edge(){
    return text[active_e] ;
}

void add_SL(int node){
    if(needSL > 0 ) tree[needSL].slink = node;
    needSL = node ;
}

bool walkdown(int node){
    if(active_len >= tree[node].edge_length()){
        active_e += tree[node].edge_length() ;
        active_len -= tree[node].edge_length();
        active_node = node ;
        return true ;
    }
    return false ;
}

void st_init(){
    needSL = remainder_ = 0 ;
    active_node = active_e = active_len = 0 ;
    pos = -1 ;

    cnt = root = 1 ;
    active_node = 1 ;
    tree[cnt++].init(-1,-1);
    return ;
}

void st_extend(char c){
    pos++ ;
    needSL = 0 ;
    remainder_++ ;
    while(remainder_ > 0){
        if(active_len == 0 ) active_e = pos ;
        if(tree[active_node].next[active_edge()] == 0){
            int leaf = cnt ;
            tree[cnt++].init(pos) ;
            tree[active_node].next[active_edge()] = leaf ;
            add_SL(active_node) ;
        }
        else{
            int nxt = tree[active_node].next[active_edge()] ;
            if(walkdown(nxt)) continue ;
            if(text[tree[nxt].start + active_len] == c){
                active_len++ ;
                add_SL(active_node) ;
                break ;
            }

            int split = cnt;
            tree[cnt++].init(tree[nxt].start , tree[nxt].start + active_len) ;
            tree[active_node].next[active_edge()] = split ;
            int leaf = cnt;
            tree[cnt++].init(pos) ;
            tree[split].next[c] = leaf ;
            tree[nxt].start += active_len ;
            tree[split].next[text[tree[nxt].start]] = nxt ;
            add_SL(split) ;
        }
        remainder_-- ;
        if(active_node == root && active_len > 0){
            active_len--;
            active_e = pos - remainder_ + 1 ;
        }
        else{
            active_node = tree[active_node].slink > 0 ? tree[active_node].slink : root ;
        }
    }
    return ;
}

void debug(){
    for(int i = 0 ; i < cnt ; i++){
        cout << i << ' ' << tree[i].start << ' ' << tree[i].end << ' ' << tree[i].slink << '\n' ;
        for(auto it : tree[i].next){
            cout << it.first << ' ' << it.second << '\n' ;
        }
    }
    return ;
}

void lrs_dfs(int r , int len , int repeats){
    for(auto it : tree[r].next){
        lrs_dfs(it.second , len + tree[r].edge_length() , tree[r].next.size()) ;
    }
    if(tree[r].slink == 0 && len > max_lrs){
        lrs_repeat = repeats ;
        max_lrs = len ;
        lrs_index = tree[r].start - len ;
    }
    return ;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
#endif // LOCAL
    int n ;
    cin >> n ;
    while(n--){
        cin >> text ;
        st_init() ;
        text += "$" ;
        oo = text.length() ;
        for(int i = 0 ; i < text.length() ; i++) st_extend(text[i]);

        max_lrs = lrs_index = lrs_repeat = 0 ;
        lrs_dfs(root,0,0) ;
        cout << max_lrs << '\n' ;
    }

    return 0;
}