###### tags: `CP`

# [CP] 常用的算法 & 結構
### KMP
- 在字串s中，找到所有子串p的位置
- 說明
- 使用時，直接傳入字串s和子串p。
- 所有子字串會在ids裡面找到
- 查看這些id可以用print()
- 程式碼

class KMP_t{
public:
    vt<ll> LPS;
    vt<ll> ids;
    string s,p;
    KMP_t(string s, string p){
        this->s = s;
        this->p = p;
        LPS.clear();
        ids.clear();
        match();
    }
    void build_FPS(){
        ll head = 0;
        LPS[0] = 0;
        for(ll j = 1; j<p.size(); ++j){
            while(head>0 && p[head]!=p[j]){
                head = LPS[head-1];
            }
            if(p[head]==p[j]){
                head++;
                LPS[j] = head;
            }
        }
    }
    void match(){
        ll ns = s.size(), np = p.size();
        LPS = vt<ll>(np, 0);
        build_FPS();
        ll i = 0, j = 0;
        while(i<ns && j<np){
            if(s[i]==p[j]){
                j++;
                i++;
            }
            else if(j<=0){
                i++;
            }
            else{
                j = LPS[j-1];
            }
            if(j==np){
                ids.push_back(i-np); 
                j = LPS[j-1];
            }
        }
    }
    void print(){
        for(auto& e:ids){cout<<e<<" ";}
        cout<<endl;
    }
};

- 時間複雜度：$O(|p|+|s|)$

---

### DSU
- Union Find優化
- 平均常數複雜度 / 每個操作

#include "bits/stdc++.h"
#define ll long long
#define vt vector
#define pb push_back

#define fir first
#define sec second
#define mp make_pair
#define endl '\n'
#define double long double
using namespace std;
/*---------------------copy from here---------------------*/
namespace DSU{
    class DSU{
    public:
        vt<ll> p;
        vt<ll> sz;
        DSU(int N){
            p.resize(N);
            sz.resize(N);
            for(int i = 0; i<N; ++i){p[i] = i;sz[i] = 1;}
        }
        int find(int x){
            if(p[x]==x){return x;}
            return p[x] = find(p[x]);
        }
        void Umerge(int x, int y){
            int px = find(x);
            int py = find(y);
            if(px==py){return;}
            if (sz[px] < sz[py])swap(px, py);
            p[py] = px;
            sz[px]+=sz[py];
        }
        void merge(int x, int y){
            int px = find(x);
            int py = find(y);
            p[py] = px;
            sz[px]+=sz[py];
        }
    };
}
/*---------------------copy to here---------------------*/

---

### Factorial
- Frac數組為階乘
- C為排列組合的$C^n_r$

namespace factorial{
    const ll mxN = 1e5+1LL, mod = 1e9+7LL;
    ll fac[mxN];
    void fill_fac(){
        fac[0] = fac[1] = 1LL;
        for(ll i = 2; i<mxN; ++i){
            fac[i] = fac[i-1]*i;
            fac[i]%=mod;
        }
    }
    ll C(ll n, ll r){
        if(r==0){return 1LL;}
        ll v = fac[r]*fac[n-r]%mod;
        ll inv_ele = pow(v, mod-2, mod);
        return (inv_ele*fac[n])%mod;
    }
}

---
### Segment tree
- 離散版
- 範例中是區間和，要改其他的可以動`what`函數

namespace segtree{
    class segtree_node {
        public:
            ll s = -1, e = -1, val = 1e9 + 1;
            segtree_node* left = nullptr,* right = nullptr;
            segtree_node(ll val, ll s, ll e) {
                this->val = val;
                this->s = s, this->e = e;
            }
            segtree_node(ll val, ll s, ll e, segtree_node* left, segtree_node* right) {
                this->val = val;
                this->s = s, this->e = e;
                this->left = left, this->right = right;
            }
        };
        ll what(ll x, ll y) {
            return x + y;
        }
        segtree_node* build_segtree(ll s, ll e, const vt<ll>& a) {
            //check({ s, e });
            if (s == e) {
                segtree_node* new_node = new segtree_node(a[s], s, s);
                return new_node;
            }
            ll mid = (s + e) >> 1;
            segtree_node* left = build_segtree(s, mid, a);
            segtree_node* right = build_segtree(mid + 1, e, a);
            segtree_node* root = new segtree_node(what(left->val, right->val), s, e, left, right);
            return root;
        }
        void update_segtree(segtree_node* root, ll id, ll val, const vt<ll>& a) { // a is useless
            if (root->s == root->e && root->s == id) {
                root->val = val;
                return;
            }
            ll mid = (root->s + root->e) >> 1;
            if (id <= mid) {
                update_segtree(root->left, id, val, a);
            }
            else if (id > mid) {
                update_segtree(root->right, id, val, a);
            }
            root->val = what(root->left->val, root->right->val);
        }
        ll query_sum(segtree_node* root, ll L, ll R) {
            if (root->s == L && root->e == R) { return root->val; }
            ll mid = (root->s + root->e) >> 1;
            //check({ root->s, root->e, mid,L, R });
            if (L > mid) { //the range is totally at root->right
                return query_sum(root->right, L, R);
            }
            else if (R <= mid) {//the range is totally at root->left
                return query_sum(root->left, L, R);
            }
            else {
                return what(query_sum(root->left, L, mid), query_sum(root->right, mid + 1, R));

            }
    }
}


int main() {

}