UVa760 - DNA Sequencing (最長共同前綴 Longest Common Prefix)

題目大意：

給你兩組字串，想請你找出裡面其中最長的共同子字串，如果有複數最長的子字串則透過字典序輸出。

注意：這題的輸出格式有特別要求

分析：

這題使用 Suffix Array 來找出最長共同前綴 Longest Common Prefix 是我認為最理想的解法，將兩組字串結合後透過 Suffix Array 的後綴排序來找出最長共同前序可以有效的把此問題給解決。

如果不懂 Suffix Array or Longest Common Prefix 可以參考此演算法說明，因為我的這演算法說明基本上是用此題進行範例，我想會加速你再學習的腳步，如果我的寫作可以讓你好理解的話XD。

學會了 Suffix Array 與理解 LCP 原理後就可以把這題解決掉了！

焦點回到題目上，解開題目的小設計

QUESTION : 題目是要找出兩組字串中最長的共同子字串，跟 LCP 有甚麼關係呢？

當你把兩組字串結合成一組字串後透過 Suffix Array + LCP 的特性就可以找出相似前綴，舉個例子好了：
有兩組字串 atgc , tga，我們用兩個比英文小寫字母還小的符號去連接他們則 Suffix Array 看起來會像這樣：
merge string : atgc$tga#
Suffix Array is:

index	string	sa[i]
1	#	9
2	$tga#	5
3	a#	8
4	atgc$tga#	1
5	$tga#	4
6	ga#	7
7	gc$tga#	3
8	tga#	6
9	tgc$tga#	2

是不是知道 LCP 怎麼用了，對吧！不知道該打

之後透過 sa[i] 的值查詢他們分布在哪個位置，如果兩個都分布在 \($\) 字號前面則代表他們其實都是第一組字串的子字串，並不是我們要的答案，反之如果都分布在 \($\) 字號後面亦是如此。但如果其中一個在 \($\) 字號前面而另一個在 \($\) 和 # 字號的中間就代表這兩組字串都有此子字串這就是我們要的答案！P.S. # 字號似乎沒辦法給他 mathjax

於是第一次迴圈先找出 max_lcp，第二次迴圈找出長度等於 max_lcp 的子字串輸出。

值得需要小注意的就是題目有要求我們要用字典序輸出，但由於 Suffix Array 特性已經幫我們做好所以我們就不需要特別在留意，但還是需要注意到有可能會是重複輸出，即此子字串可能在兩個字串中都重複兩次，所以需要用 map 來檢查。

如果還是不懂就讓我用程式碼來輔助吧！

// 找出 max_lcp 的長度
for(int i = 1 ; i <= n ; i++){
    if((sa[i] < lenA && sa[i-1] < n+1 && sa[i-1] > lenA ) ||
        (sa[i] > lenA && sa[i-1] < n+1 && sa[i-1] < lenA))
        // 檢查結合的 string 共同前綴是不是都是同一個題目字串的
        max_lcp = max(max_lcp , lcp[i]);
}

// 輸出長度等於 max_lcp 的子字串
map<string,int> mp ;
if(max_lcp == 0) //如果是 0 就輸出題目要求格式
    {cout << "No common sequence.\n" ; return ;}
for(int i = 1 ; i <= n ; i++){
    if((sa[i] < lenA && sa[i-1] < n+1 && sa[i-1] > lenA ) ||
       (sa[i] > lenA && sa[i-1] < n+1 && sa[i-1] < lenA))
       // 檢查結合的 string 共同前綴是不是都是同一個題目字串的
       if(lcp[i] == max_lcp){
            string temp = strA.substr(sa[i] , max_lcp);
            if(mp[temp]) continue ; //檢查有沒有重複輸出
            else mp[temp] = 1 ; //紀錄已經被輸出過
            cout << temp << '\n' ;
       }
}

強烈建議搭配演算法知識 - Suffix Array 後綴陣列，裡面的程式碼基本上都是配合這題而寫的非常建議讀者學會。

參考連結

快速冪 OI wiki
UVa 760 – DNA Sequencing
常用ASCII码详细对照表 （0—255）

心得

這題的學習難度好高阿…，這題我應該總讀書時間應該有高達 8 小時了吧ಥ⌣ಥ！嗚嗚，我真笨，希望我未來在學習演算法的路上狀況可以越來越好，也可以磨練好我自學的能力，這很重要，讀書基本上只需要百分之 20% 與老師溝通剩下的都是需要學生自己去摸索探討，希望我未來可以找到好老師讓我成長，在我自學學到盲點時可以幫助我一把。

題外話，CSDN 與大陸資源真的是我學習的主要材料呀，大陸在於資訊的知識比起台灣多蠻多的，這樣也讓我在自學演算法的路上輕鬆了些很謝謝大家都願意把技術下放給我們這些菜鳥。

補足我身心的缺陷，讓我更加優秀、生活更加快樂應該是我人生中的其中一個目的吧！XD

題目程式碼

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

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

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define N 2000
using namespace std;
string strA="" , strB="" , strC="" ;
int sa[N] , rk[N<<1] , oldrk[N<<1] , id[N] , cnt[N] ;
int n , m , maxn , lenA , lenB , flag =0 ;

void build_sa(){
    int i , m , p , w ;
    n = strA.length()-1 ;
    m = max(n , 300 );
    memset(cnt,0,sizeof(cnt));
    memset(rk,0,sizeof(rk));
    for(i = 1 ; i <= n ; i++) ++cnt[rk[i] = (int)strA[i]] ;
    for(i = 1 ; i <= m ; i++) cnt[i] += cnt[i-1] ;
    for(i = n ; i >= 1 ; i--) sa[cnt[rk[i]]--] = i ;

    for(w = 1 ; w < n ; w <<= 1){
        memset(cnt,0,sizeof(cnt));
        for(i = 1 ; i <= n ; i++) id[i] = sa[i] ;
        for(i = 1 ; i <= n ; i++) ++cnt[rk[id[i]+w]] ;
        for(i = 1 ; i <= m ; i++) cnt[i] += cnt[i-1] ;
        for(i = n ; i >= 1 ; i--) sa[cnt[rk[id[i]+w]]--] = id[i] ;

        memset(cnt, 0 , sizeof(cnt));
        for(i = 1 ; i <= n ; i++) id[i] = sa[i] ;
        for(i = 1 ; i <= n ; i++) ++cnt[rk[id[i]]] ;
        for(i = 1 ; i <= m ; i++) cnt[i] += cnt[i-1] ;
        for(i = n ; i >= 1 ; i--) sa[cnt[rk[id[i]]]--] = id[i] ;

        memcpy(oldrk , rk , sizeof(rk));
        for(p = 0 , i = 1 ; i <= n ; i++){
            if(oldrk[sa[i]] == oldrk[sa[i-1]] &&
               oldrk[sa[i] + w] == oldrk[sa[i-1] + w])
                rk[sa[i]] = p ;
            else
                rk[sa[i]] = ++p ;
        }
    }

    //debug
//    cout << "Suffix Array is:\n" ;
//    for(int i = 1 ; i <= n ; i++){
//        cout << i << ' ' << strA.substr(sa[i]) << ' ' <<sa[i] << '\n' ;
//    }
}

void build_lcp(){
    int lcp[N] = {} ;
    int max_lcp = 0 ;
    for(int i = 1 , k = 0 ; i <= n ; i++){
        if(k) k-- ;
        while(strA[i+k] == strA[sa[rk[i]-1]+k]) ++k ;
        lcp[rk[i]] = k ;
    }

    for(int i = 1 ; i <= n ; i++){
        if((sa[i] < lenA && sa[i-1] < n+1 && sa[i-1] > lenA ) ||
            (sa[i] > lenA && sa[i-1] < n+1 && sa[i-1] < lenA))
            max_lcp = max(max_lcp , lcp[i]);
    }

    //debug
//    cout << "max_lcp is " << max_lcp << '\n' ;
//    for(int i = 0 ; i <= n ; i++)
//        cout << i << ' ' << lcp[i] << '\n' ;
//    cout << "lenA =" << lenA << "\nn is" << n << '\n' ;

    if(flag)
        cout << '\n' ;
    flag = 1 ;

    map<string,int> mp ;
    if(max_lcp == 0)
        {cout << "No common sequence.\n" ; return ;}
    for(int i = 1 ; i <= n ; i++){
        if((sa[i] < lenA && sa[i-1] < n+1 && sa[i-1] > lenA ) ||
           (sa[i] > lenA && sa[i-1] < n+1 && sa[i-1] < lenA))
           if(lcp[i] == max_lcp){
                string temp = strA.substr(sa[i] , max_lcp);
                if(mp[temp]) continue ;
                else mp[temp] = 1 ;
                cout << temp << '\n' ;
           }
    }
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    //freopen("out.txt" , "w" , stdout );
#endif // LOCAL

    while(cin >> strA >> strB){
        lenA = strA.length()+1;
        lenB = strB.length();
        strA = ' ' + strA + '$' + strB + '#' ;
        //debug
        //cout << "strA is " <<strA << "\nstrA.length() is " << strA.length() << '\n' ;

        build_sa();
        build_lcp();
    }

    return 0;
}