• Ref:

資料結構

樹狀結構

Disjoint Set

#define MAXN 1000005

int parent[MAXN];//每個點紀錄其父母節點
int sz[MAXN];//每個點紀錄以它為根的子樹的大小

void Make_Set(int x){
    parent[x] = x;
    sz[x] = 1;
}

void Init(int n){
    for(int i = 1; i <= n; i++){
        Make_Set(i);
    }
}

int Find_SET(int x){
    if(parent[x] == x)return x;
    parent[x] = Find_SET(parent[x]);
    return parent[x];
}

bool UNION_SET(int x, int y){
    x = Find_SET(x);
    y = Find_SET(y);
    if(x == y)return false;
    if(sz[x] < sz[y])swap(x, y);
    parent[y] =  x;
    sz[x] += sz[y];
    return true;
}

樹狀數組

#define MAXN 10000

int BIT[MAXN + 1];

int lowbit(int x){
    return x & (-x);
}

int sum(int x){// sum a1~ax
	    int res = 0;
	    for(int i = x; i > 0; i -= lowbit(x) ){
	        res += BIT[i];
	    }
	    return res;
}

void modify(int x, int v){// ax += v
    for(int i = x; i <= MAXN; i += lowbit(i) ){
        BIT[i] += v;
    }
    return ;
}

字串匹配

Ref:

Algorithm - String matching

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/c53c8e3c-bb67-44d9-9497-5f1adc9815d5/4.pdf

KMP

• Ref

Time: math: O(n) Space: math: O(n)

vector<int> build_kmp(const string &P){
    vector<int> f(P.size() + 1);
    int fp = f[0] = -1;
    for(int i = 1; i < (int)P.size(); i++){
        while(~fp && P[fp + 1] != P[i])fp = f[fp];
        if(P[fp + 1] == P[i]) ++fp;
        f[i] = fp;
    }
    return f;
}

vector<int> kmp_match(vector<int> fail, const string &P, const string &T){
    vector<int> res;
    const int n = P.size();
    for(int j = 0, i = -1; j < (int)T.size(); j++){
        while(~i && T[j] != P[i + 1])i = fail[i];
        if(P[i + 1] == T[j]) ++i;
        if(i == n - 1){
            res.push_back(j - n + 1);
            i = fail[i];
        }
    }
    return res;
}

Z value

• 練習題

Trie