# データ構造テスト

## String sort
### Key-Index Counying
朝陽のパワポみる

### LSD String sort
桁に優先度を設けてソートを行う。
最上位桁が最も優先順位の高いキー、次いでその下の桁が2番目の優先順位のキー、3番目の桁が……、といった要領である。優先度が低い桁からソートを行なっていく。
長さWのN個の文字列の場合、実行時間はWNに比例 ( W<<Nのとき線形時間 O(N) )
* 例: 170, 45, 75, 90, 2, 24, 802, 66
1. 1の位においてソートを行う
* 170, 90, 2, 802, 45, 75, 66
2. 10の位においてソートを行う
* 2, 802, 24, 45, 66, 170, 75, 90
3. 100の位においてソートを行う
* 2, 24, 45, 66, 75, 90, 170, 802

### MSD string sort
LSDは最下位の桁からソートを行なったがMSDは上位の桁からソートを行う。
MSD string sortの実行時間はデータによって異なる
* ランダム入力
* 文字数に対し線形でない
* ランダムでない入力
* 実行時間はほぼ線形
* 等しいキーの数によって変更
* 最悪の入力
* 全ての文字列が等しい場合
* 文字数に対し線形

### Three-way string quick sort
* ソート済みあるいはそれに近い配列が最悪の入力
* あらかじめ配列をシャッフルすることによる改善
* 分割の基準となる文字列をランダムに選択することによる改善


## Tries
* Trieとは
* ノードにはR個のリンクを持つ
* keyにvalueを付与して挿入
* 1ノードあたり2つの子ノードを持てる

W: 検索する文字列の長さ, N: データ数, R: 文字の種類
* 利点
* 検索が成功した時の計算量がO(W)で高速(最悪計算量: O(log_n R))
* 欠点
* メモリを大量に消費 {(8R + 56)N to (8R + 56)NW}
* 文字列Wに依存
* アルファベットの数だけリンクを持つため無駄が多い

文字列を検索する場合、ルートから1文字ずつ検索
* 例1: shells => 3
* 例2: shell => Null


Trie木へのinsert
* 挿入する場合にTrie木内を検索
1. ヒットした場合 -> Valueを上書き
* sea: 2 -> 6
2. ミスした場合 -> 足りな分のノードとValueを追加

### TST
* TSTとは
* ルートを持たない
* ノードはR個のリンクを持つ
* keyにvalueを付与して挿入
* 1ノードあたり3つの子ノードを持てる

W: 検索する文字列の長さ, N: データ数, R: 文字の種類
計算量 : best O(log_R N), worst O(N)
* 利点
* 1ノードあたり3つの子ノードを持てる
* Trie木と比べメモリ消費量が抑えられている{64N to 64NW}
* 欠点
* アルファベットの数だけリンクを持つため無駄が多い

検索

TST木へのinsert
* 挿入する前にTST木内を検索した後に挿入

## Substring-search
### Brute-force Substring Search
長さNのテキスト内に含まれる長さMのパターンを探索
1. テキストとパターンを先頭から一文字ずつ比較
* 一致した場合、お互いの次の文字を比較
* 不一致の場合、比較するテキストの先頭を一つ進める

計算量:O(N), 最悪計算量:O(NM)

### Knuth-Morris-Pratt substring search
文字列: AAABAAAAA
パターン: BAAAAA
1. 4文字目まではパターンと一致(BAAA)
2. 出現する文字が{A,B}の場合、BAAABがわかる
3. パターンの先頭文字が次に出現するのはi=4
4. 次の比較をi=4から行なう

### DFA
KMP searchはDFAで実装可能．(DFAは決定性有限オートマトンを意味する)
* DFAの実装方法
* 2次元配列 dfa[ charAt(i) ][ j ] で実装
* 整数 j は現在のオートマトンの状態番号
* charAt(i) は現在参照している文字
* 配列要素はオートマトンの状態遷移先
* 下図の例では，状態0から状態1へ遷移する入力は"A"であるので，
dfa[A][0] = 1　となる．

### KMP construction
KMPにおけるDFAを真面目にシミュレートしてるだけの章
書くことなし

### Boyer-Moore Substring Search
長さNの文字列(text)中から長さMのパターン(pattern)を探索するアルゴリズム
1. パターンで用いられる文字から辞書(right)を作成
* rightはその文字が最も右にある場所のindex (存在しない場合は-1)
3. パターンの長さ分の部分文字列をテキストのi文字目から取り出し、その文字列を後ろから比較
4. パターンのj文字目が不一致の時点で、iにj - right[ text[i + j] ]を加算
5. 文字が全て一致した時点でその位置のindexを返し探索終了(存在しない場合は-1)


検索対象の文章の長さをN、パターンの文字長をMとすると計算量はO(N/M)、最悪計算量はO(NM)


### Rabin-Karp fingerprint substring search
部分文字列のハッシュ値の比較を用いた検索アルゴリズム
テキストの部分文字列のハッシュ値を計算し、パターンのハッシュ値と一致すれば探索終了。
#### Rolling Hash
文字1文字を値とし、その値と基数の積の総和をハッシュ値とするハッシュ関数を使う。

* x:ハッシュ値, t:部分文字列, R:基数, Q:素数
* 0~M文字目までの部分文字列のハッシュ値
$$x _ { i } = t _ { i } R ^ { M - 1 } + t _ { i + 1 } R ^ { M - 2 } + \ldots + t _ { i + M - 1 } R ^ { 0 } \bmod Q $$
* 1文字ずらした次のハッシュ値
$$x _ { i + 1 } = \left( x _ { i } - t _ { i } R ^ { M - 1 } \right) R + t _ { i + M } $$

* 例: abr
* a = 1, b = 2, r = 5, 基数:10
$$ abr = 1 \times 10^2 + 2 \times 10^1 + 5 \times 10^0 = 125 $$
* 文字列:babr
1. bab
$$ 2 \times 10^2 + 1 \times 10^1 + 2 \times 10^0 = 212$$
2. abr
$$ (212 - 2 \times 10^2) \times 10 + 5 = 125$$

Rolling Hashの場合、ハッシュ値の計算は初期値の計算O(M)
任意の区間の部分文字列のハッシュ値の計算はO(1)
O(N)の計算量で文字列検索が可能