EOJ 1805 POJ 217最長共通サブストリング(接尾辞配列+高さ配列)

最長共通サブストリングは最長共通サブシーケンスとは異なり、サブシーケンスは連続を要求しないが、サブストリングはその名の通り連続する必要がある.応用については,最長共通サブストリングアルゴリズムが遺伝子断片マッチングに応用できると思う.EOJ 1805上の文字列の長さは5万を超え、接尾辞配列がこの問題を解決するのにタイムアウトすることはなく、この問題を解決する唯一のアルゴリズムとも言える.構造sa配列については非常に巧みであり,RMQアルゴリズムの考え方とよく似ており(いずれも分治の考え方を用いている),まず1文字からなる列で並べ替え,さらに2文字からなる列で並べ替え,さらに4つ・・・sa配列が接尾辞(すなわち(i...L)からなる子列)で並べ替えられるまで接尾辞配列構築が完了する.コードは次のとおりです.

int k;
bool cmp(int i, int j)
{
    if (rk[i] != rk[j]) return rk[i] < rk[j];
    else {
        int ii = i + k <= n ? rk[i + k] : -1;
        int jj = j + k <= n ? rk[j + k] : -1;
        return ii < jj;
    }
}

void Construct_sa()
{
    n = s.size();
    for (int i = 0; i <= n; i++){
        sa[i] = i;
        rk[i] = i < n ? s[i] : -1;
    }
    for (k = 1; k <= n; k <<= 1)
    {
        sort(sa, sa + n + 1, cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i <= n; i++)
        {
            tmp[sa[i]] = tmp[sa[i - 1]] + cmp(sa[i - 1], sa[i]) ;
        }
        for (int i = 0; i <= n; i++){
            rk[i] = tmp[i];
        }
    }
}

接尾辞配列を構築する時間的複雑さはO(nlogn)であることが分かる.
共通サブストリングを求めるためには,高さ配列を導入せざるを得ない.すなわち,並べられた接尾辞配列に対して,隣接する2つの接尾辞の共通接頭辞長を探究する.時間を節約するために、順序付けされた接尾辞配列を使用して、共通接頭辞の長さを比較する場合、毎回シリアルヘッダから開始する必要はありません.コードは次のとおりです.

void Construct_h()
{
    n = s.size();
    for (int i = 0; i <= n; i++) rk[sa[i]] = i;
    int k = 0;
    for (int i = 0; i < n; i++){
        int j = sa[rk[i] - 1];
        if (k) k--;//    
        for ( ; j + k < n&&i + k < n&&s[j + k] == s[i + k]; k++);
        h[rk[i] - 1] = k;
    }
}

証明:h配列には以下の性質がある:h[i]≧h[i-1]-1
suffix(j)をsuffix(i−1)の上位に並ぶ接尾辞とすると、それらの最長共通接頭辞はh[i−1]である.h[i-1]>1の場合、suffix(j)を「abcde...」suffix(i-1)を「abdef...」とし、前後対照で最も長い共通プレフィックス長が2であることがわかり、suffix(i)=「bdef...」を考慮すると、では、その前に並んでいる場合、suffix(j+1)=「bcef.」という下限があります.suffix(j+1)がsuffix(i)の直前に並んでいる場合、彼らの最長共通接頭辞=1であり、h[i]=h[i-1]-1である.suffix(j+1)がsuffix(i)の前に並べられず、suffix(j+1)とsuffix(i)の間にsuffix(k)が挿入されると、suffix(k)はsuffix(j+1)よりも大きく、suffix(i)よりも小さくなることが予想され、その最初の文字は必ず「b」であり、2番目の文字は必ず「c」と「d」の間にあり、suffix(k)とsuffix(i)の最長共通接頭辞>=suffix(j+1)とsuffix(i)の最長共通接頭辞は、h[i]≧h[i−1]−1が一定に成立することが分かる.一方、h[i-1]<=1の場合、h[i-1]-1<=0であり、h[]配列の定義から分かるように、h[i]>=0であるため、h[i]≧h[i-1]-1は一定に成立する.
h[1],h[2],......,h[n]の順に計算すると,h配列の性質を利用して時間複雑度をO(n)に下げることができる.
その後の操作はmain関数で実現され、与えられた2つの文字列に対して、その間に2つの文字列に現れない文字(スペースなど)を加えて1つの文字列に連結し、sa配列の構築とh配列の計算を行う.sa[i]とsa[i+1]が2つの文字列に属する前提の下で、h[i]の最大値を探し出して、つまりテーマのanswerです!
コアコードは次のとおりです.

Construct_sa();
Construct_h();
int len = s.size();
int ans = 0;
for(int i=0; iif((sa[i] < len1) != (sa[i+1] < len1))//len1         
         ans=max(ans,h[i]);

複数の列の最長共通サブ列については?2点を使うには、後で詳しく話します.(by Datow)