大事だけど、すぐ忘れてしまう、そんなアルゴリズムたち

Rolling-Hash(ローリングハッシュ)

https://www.slideshare.net/hcpc_hokudai/rolling-hash-60984153
文字列に数値を割り当てる方法。アリ本の上級編に書いてあったので順次やっていきたい。

Union-Find木

グラフの管理をできる。始め頂点がバラバラの状態から接合していきそれぞれのグループに分けていくのが得意。

UnionFind.cpp

class UnionFind {
public:
    //親の番号を格納する。親だった場合は-(その集合のサイズ)
    vector<int> Parent;

    //作るときはParentの値を全て-1にする
    //こうすると全てバラバラになる
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }

    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }

    //自分のいるグループのノード数を調べる
    int size(int A) {
        return -Parent[root(A)];//親をとってきたい]
    }

    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }

        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらひっくり返しちゃう。
        if (size(A) < size(B)) swap(A, B);

        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;

        return true;
    }
};

二分探索木

左の子孫の値 ≤ 親 ≤ 右の子孫の値」という制約を持つ二分木のこと。
計算量はO(log(N))。二分探索を木にしてやっている感じ。

組み合わせ(nCk)

http://keita-matsushita.hatenablog.com/entry/2016/11/30/111110
組み合わせの値がパスカルの三角形内の数値に相当しているという性質から動的計画法を用いて、組み合わせを求める方法。計算量はO(N^2)だが、配列として値を格納できるので毎回nCkを計算しなくて済む。

combi.cpp

int comb(int n, int k){
    int table[n+1][n+1];
    for( int i=0; i<=n; i++ ) table[i][0]=1;
    for( int i=1; i<=k; i++ ) table[i][i]=1;

    for(int i=2; i<=n; i++){
        for(int j=1; j<min(i, k+1); j++){
            table[i][j]=table[i-1][j-1]+table[i-1][j];
        }
    }
    return table[n][k];
} 

int main(){
    cout << comb(6,2) << endl; //15
    cout << comb(3,1) << endl; //3
    cout << comb(12,3) << endl; //220

    return 0;
}

z-algorithm

http://drken1215.hatenablog.com/entry/2019/09/16/014600
ABC141を例に
Suffix Array
Z-algorithm
ローリングハッシュ + 二分探索
「ローリングハッシュ + 二分探索」の高速化
DP
の5通りを実装している

suffix-array

アリ本の上級編に書いてあったので順次やっていきたい。
SA-ISという強力なやつがあるらしい。