【文字列データ構造拡張シリーズPart 1】拡張子配列学習ノート

5539 ワード
かって気ままにやる サフィックス配列 文字列 データ構造
AC自动机がすごいですね.だから私は后述自动机と后述配列を勉强したいです.大丈夫です.これは邪魔になりません.
——————————————–線割は私です.w方法によって文字列マッチングアルゴリズム/データ構造はプレフィックスとサフィックスの二つの種類に分けられています.プレフィックスはACのモチーフで、KMPとTrieが一番有名です.サフィックスの代表的なものはサフィックスのモチーフ/サフィックスの木です.私はサフィックスを学んで私を咬みます.www
まずいくつかの定義をします.(≧▽≦)/～一.通常はΣで1つの文字セット(各要素は1文字です.)を表します.その中の文字はそれぞれ違います.その中の文字は2つの間で比較可能です.2.文字列はΣの中のいくつかの文字列から一定の順序で配列されています.長さはnの文字列sで、その長さはlen(s)とします.シリアルSのi番目の文字はs[i].3.文字列sのi番目からj番目までの連続文字で構成された文字列はsの一列と呼ばれています.注意してください.空列もsの一列としてカウントされます.四.sのi番目の桁を選択すると、第一位からi番目の部分列までsの一つのプレフィックスと呼びます.対応するi番目からn番目の部分まで構成された部分列を5つの比較原則といいます.は、2つの列s 1、s 2の第一位から順に後へ比較し、文字s 1[i]>s 2[i]があれば、列s 1の字典順は串s 2より大きく、s 1[i]基礎知識は終わりました.サフィックス配列ということを始めます.サフィックス配列というのは、文字列のすべてのサフィックスを辞書順に小さい順に並べ替えて、サアという配列を作ります.sa[i]は並べ替え後のi番目の文字列が表すサフィックスは元の列の何番目から始まります.Suffix[i]を使ってi]i位からのサフィックスを表します.明らかです.
Suffix[sa[i]拡張子配列は単独では出現しません.それと同時に順位配列を使います.
順位配列:順位配列のrankを定義すると、rank[i]は元の列の中でi番目の位の初めの日記の後綴りを表します.すべての後綴りの中で辞書の順序は小さい時から長い列のいくらまでですか?
したがって、拡張子配列saとrankは実は一対の逆演算です.
どうして互いに反逆しますかSA[i]=jがあれば、Rank[j]=i
ですから、この二つの配列はどちらかを求めさえすればいいです.
O(n)のは他のものを求めます.
じゃ問題が来ました.どうやって拡張配列を作りますか?明らかに一番裸の考えは全部の拡張子を作って並べ替えてからやりましょう.==しかし明らかにQQはだめです.2つの文字列を比較するとO(n)です.並べ替えはO(n 2)になります. lognこんなに遅いなら、あなたは何を使いますか?┻┻┻┻そこで人々は2つの方法を出しました.DA(倍増)とDC 3アルゴリズムです.
拡張子配列:文字列sの各ビットから、あるビットから2 kのサブストリングを取って、サブストリングを並べ替えて、rankを求めます.サブストリングが十分長いと、このサブストリングは列全体の後綴りになります.しかし、倍増する時、私達はすべての列を取り出す必要はありません.以前のrankの貢献はまだ残っていますので、2 k−1のサブストリングのrank(2 k−1列のrank 2つとも記録してください)を新たに倍増させるだけで、2 k列のrankを得ることができます.加速するためには、並べ替えの際に基数並べ替えを使います.(すぐにロゴを追加してください.)
次に私達に酸味のさわやかなコードを体得させます.多くの人が拡張子配列を構築するコードを見たことがあると信じています.
膜の羅穂は高く昇って論文を書いて、論文の中でコードの書き方は多くの方面ですべて劉汝佳の訓練マニュアルの書き方より優れています.
#include
using namespace std;
#define MAXN 100010
char s[MAXN];
int A[MAXN];
//        ,   s         .s A       0-n-1 
int sa[MAXN],rank[MAXN];//     rank sa
int Count[MAXN];//        
int l[MAXN],r[MAXN],tmp[MAXN];//           ,r            ,l    rank . 
int n,maxn;//     
bool comp(int *A,int a,int b,int len)//      
{
    return A[a]==A[b]&&A[a+len]==A[b+len];
}
int main()
{
    /*          */
    int i,j,k,*x=l,*y=r;//       l,r         
    for (i=0;i0;
    for (i=0;i//        
    for (i=1;i1];
    for (i=n-1;i>=0;i--)    sa[--Count[x[i]]]=i;//   sa 
    for (k=1,i=1;i1,maxn=i)
    {
        for (i=0,j=n-i;j//       
        for (j=0;jif (sa[j]>=k)   y[i++]=sa[j]-k;
        for (j=0;jfor (j=0;j0;
        for (j=0;jfor (j=1;j1];
        for (j=n-1;j>=0;j--)    sa[--Count[tmp[j]]]=y[j];//  sa 
        for (swap(x,y),i=1,x[sa[0]]=0,j=1;j1],sa[j],k)?i-1:i++;//  rank
        //             rank   ,                 rank 
        //  y        sa     (       ),      y  rank 
    }
}
SAの応用はSAMの後で単独でブログを書くつもりです.
データ構造:マルチツリーの確立