String

Hash

Primes table

1E3 1E6 1E9 1E18
1009 1000003 1000000021 1000000000000000003
1013 1000033 1000000033 1000000000000000009
1019 1000037 1000000933 1000000000000000031
1021 1000039 1000000993 1000000000000000079

Random Hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 随机 hash
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const vector<int> MOD = {
    1000000021, 
    1000000033,
    1000000087,
    1000000093,
    1000000097,
    1000000933,
    1000000993,
};

const vector<int> BASE = {
    10007,
    10009,
    10037,
    10039,
    10061,
    10067,
    10069,
};

int GetMod() {
    return MOD[rng() % MOD.size()];
};

int GetBase() {
    return BASE[rng() % BASE.size()];
}

int Mod = GetMod();
int Base = GetBase();

// [1, n] 直接传 s
template<class T = std::string>
struct Hash {
    int n;
    const int mod, base;
    std::vector<long long> power, key;
    Hash(const T& s, int _mod, int _base) : mod(_mod), base(_base) {
        n = s.size();
        power.resize(n + 1);
        key.resize(n + 1);
        power[0] = 1;
        for(int i = 1; i <= n; i++){
            power[i] = power[i - 1] * base % mod;
            key[i] = (key[i - 1] * base + s[i - 1]) % mod;
        }
    }

    int get(int l, int r){// 下标从 1 开始
        return ((key[r] - key[l - 1] * power[r - l + 1]) % mod + mod) % mod; 
    }
};

Sequence Hash

2024/1/18 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// [1, n] 直接传 s
template<int mod = 1000000993, int base = 10333, class T = std::string>
struct Hash {
    std::vector<long long> power, key;
    Hash(const T& s){// 直接传 s
        power.resize(1, 1);
        key.resize(1, 0);
        extend(s);
    }

    void extend(const T& s){
        for(int i = 0; i < s.size(); i++){
            power.push_back(power.back() * base % mod);
            key.push_back((key.back() * base + s[i]) % mod);
        }
    }

    void pop(){
        power.pop_back();
        key.pop_back();
    }

    int get(int l, int r) const {// 下标从 1 开始
        return ((key[r] - key[l - 1] * power[r - l + 1]) % mod + mod) % mod; 
    }
};

Set Hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 集合 Hash 只关心元素种类，个数 （顺序无关）
template<int mod = 1000000993, int base = 10333, class T = int>
struct Hash {
    int key;
    vector<int> power;
    Hash(int n){ // 集合最大元素
        power.resize(n + 1, 1);
        for(int i = 1; i <= n; i++){
            power[i] = (long long) power[i - 1] * base % mod;
        }
        key = 0;
    }

    void push(const T& val){
        key += power[val];
        if(key > mod){
            key -= mod;
        }
    }

    void pop(const T& val){
        key -= power[val];
        if(key < 0){
            key += mod;
        }
    }

    int get(){
        return key;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 集合 Hash 只关心元素种类，个数 （顺序无关）
template<int mod = 1000000993, int base = 10333, class T = int>
struct Hash {
    int key;
    vector<int> power;
    // n -> 集合最大元素
    Hash(int n){ 
        power.resize(n + 1, 1);
        for(int i = 1; i <= n; i++){
            power[i] = (long long) power[i - 1] * base % mod;
        }
        key = 0;
    }
    // 增加元素 val
    void push(const T& val){
        key += power[val];
        if(key >= mod){
            key -= mod;
        }
    }
    // 删除元素 val
    void pop(const T& val){
        key -= power[val];
        if(key < 0){
            key += mod;
        }
    }
    // Hash key
    int get(){
        return key;
    }    
    // 集合合并
    void merge(const Hash<mod, base, T>& h){
        key += h.key;
        if(key >= mod){
            key -= mod;
        }
    }
    // 集合相减
    void remove(const Hash<mod, base, T>& h){
        key -= h.key;
        if(key < 0){
            key += mod;
        }
    }
    // 集合清空
    void clear(){
        key = 0;
    }
    // 集合相等
    bool operator==(const Hash<mod, base, T>& h) const {
        return key == h.key;
    }
};

Trie

Prefix Trie

2024/1/20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
template<int N = 26, int offset = -'a', class T = std::string>
struct Trie {
    int cnt;
    Trie<N, offset, T>* next[N];
    Trie(){
        cnt = 0;
        for(int i = 0; i < N; i++){
            next[i] = 0;
        }
    }

    void insert(const T& s){
        Trie<N, offset, T>* cur = this;
        for(int i = 0; i < s.size(); i++){
            if(cur->next[s[i] + offset] == 0){
                cur->next[s[i] + offset] = new Trie<N, offset, T>();
            }
            cur = cur->next[s[i] + offset];
            cur->cnt++;
        }
    }

    int count(const T& s){
        Trie<N, offset, T>* cur = this;
        for(int i = 0; i < s.size(); i++){
            if(cur->next[s[i] + offset] == 0){
                return 0;
            }
            cur = cur->next[s[i] + offset];
        }
        return cur->cnt;     
    }

    bool exist(const T& s){
        return count(s) != 0;
    }
};

Xor Trie

2024/1/20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
template<int N>
struct XorTrie {
    XorTrie* next[2];
    XorTrie(){
        next[0] = 0;
        next[1] = 0;
    }

    void insert(long long x){
        XorTrie* cur = this;
        for(int i = N - 1; i >= 0; i--){
            if(cur->next[(x >> i) & 1] == 0){
                cur->next[(x >> i) & 1] = new XorTrie();
            }
            cur = cur->next[(x >> i) & 1];
        }
    }

    long long query(long long x){
        long long ans = 0;
        XorTrie* cur = this;
        for(int i = N - 1; i >= 0; i--){
            if(cur->next[((x >> i) & 1) ^ 1LL] != 0){
                cur = cur->next[((x >> i) & 1) ^ 1LL];
                ans |= 1LL << i;
            }else{
                cur = cur->next[(x >> i) & 1];
            }
        }
        return ans;
    }
};

KMP

2024/1/27

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// [1, n]  直接传 s
vector<int> get_next(string s){
    int n = s.size();
    s = "#" + s;
    vector<int> next(n + 1);
    for(int i = 2, j = 0; i <= n; i++){// 真前缀
        while(j != 0 && s[i] != s[j + 1]){
            j = next[j];
        }
        if(s[i] == s[j + 1]){
            j++;
        }
        next[i] = j;
    }
    return next;
}

// [1, n]  直接传 text, pattern
vector<int> kmp(string text, string pattern){
    int n = text.size();
    int m = pattern.size();
    vector<int> res;
    vector<int> next = get_next(pattern);
    text = "#" + text;
    pattern = "#" + pattern + "#";
    for(int i = 1, j = 0; i <= n; i++){
        while(j != 0 && text[i] != pattern[j + 1]){
            j = next[j];
        }
        if(text[i] == pattern[j + 1]){
            j++;
        }
        if(j == m){
            res.push_back(i - m + 1);
        }
    }
    return res;
}

trick

设 $f(str)$ 表示 $str$ 最长前后缀长度

给定字符串 $s$ ，在 $s$ 前后各增加一个字符变为新串 $t$ ，则 $f(t) \le f(s) + 2$ ，暴力从大到小枚举 $f(t)$ 看是否合法，假设操作 $n$ 次，复杂度 $O(n)$
$$
f(t) = f(s) + 2
$$

$$
while (t_{1, f(t)} \neq t_{n - f(t) + 1, n}) \quad f(t) –
$$

EXKMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// [1, n] 直接传 s
vector<int> exkmp(string s) {
    int n = s.size();
    s = "#" + s;
    vector<int> z(n + 1);
    z[1] = n;
    for (int i = 2, l = 1, r = 1; i <= n; i++) {
        if (i <= r) {
            z[i] = min(z[i - l + 1], r - i + 1);
        }

        while (i + z[i] <= n && s[1 + z[i]] == s[i + z[i]]) {
            z[i]++;
        }

        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

Manacher

time:2024/1/31

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// i % 2 == 1 -> d[i] / 2 * 2 - 1
// i % 2 == 0 -> d[i] / 2 * 2
vector<int> manacher(const string& s, char obstacle = '#') {
    string t;
    t += obstacle;
    for (int i = 0; i < s.size(); i++) {
        t += s[i];
        t += obstacle;
    }

    int n = t.size();
    vector<int> d(n);
    for (int i = 0, l = 0, r = 0; i < n; i++) {
        if (i <= r) {
            d[i] = min(d[r - i + l], r - i + 1);
        }

        while (0 <= i - d[i] && i + d[i] < n && t[i - d[i]] == t[i + d[i]]) {
            d[i]++;
        }

        if (i + d[i] - 1 > r){
            l = i - d[i] + 1;
            r = i + d[i] - 1;
        }
    }

    return d;
}

Suffix_Array

$author$ : $Heltion$

$range$ : $[0, n - 1]$

$p$ ： 排序后 $suffix$ 在原 $s$ 中的开头位置

$rank$ ： 排序后以 $s[i]$ 开头的 $suffix$ 的排名

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct Suffix_Array {
    vector<int> p, rank;
    Suffix_Array(string s) {
        int n = s.size(), k = 0;
        p.resize(n);
        rank.resize(n);
        vector<int> q, count;
        for (int i = 0; i < n; i += 1) p[i] = i;
        ranges::sort(p, {}, [&](int i) { return s[i]; });
        for (int i = 0; i < n; i += 1) rank[p[i]] = i and s[p[i]] == s[p[i - 1]] ? rank[p[i - 1]] : k++;
        for (int m = 1; m < n; m *= 2) {
            q.resize(m);
            for (int i = 0; i < m; i += 1) q[i] = n - m + i;
            for (int i : p)
                if (i >= m) q.push_back(i - m);
            count.assign(k, 0);
            for (int i : rank) count[i] += 1;
            for (int i = 1; i < k; i += 1) count[i] += count[i - 1];
            for (int i = n - 1; i >= 0; i -= 1) p[count[rank[q[i]]] -= 1] = q[i];
            auto cur = rank;
            cur.resize(2 * n, -1);
            k = 0;
            for (int i = 0; i < n; i += 1) rank[p[i]] = i and cur[p[i]] == cur[p[i - 1]] and cur[p[i] + m] == cur[p[i - 1] + m] ? rank[p[i - 1]] : k++;
        }
    }
};

$$
引理 \quad height[rank[i]] \ge height[rank[i - 1]] - 1
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct Suffix_Array {
    vector<int> p, rank, height;
    Suffix_Array(string s) {
        int n = s.size(), k = 0;
        p.resize(n);
        rank.resize(n);
        height.resize(n);
        vector<int> q, count;
        for (int i = 0; i < n; i++) p[i] = i;
        ranges::sort(p, {}, [&](int i) { return s[i]; });
        for (int i = 0; i < n; i++) rank[p[i]] = i and s[p[i]] == s[p[i - 1]] ? rank[p[i - 1]] : k++;
        for (int m = 1; m < n; m <<= 1) {
            q.resize(m);
            for (int i = 0; i < m; i++) q[i] = n - m + i;
            for (int i : p)
                if (i >= m) q.push_back(i - m);
            count.assign(k, 0);
            for (int i : rank) count[i] += 1;
            for (int i = 1; i < k; i++) count[i] += count[i - 1];
            for (int i = n - 1; i >= 0; i--) p[count[rank[q[i]]] -= 1] = q[i];
            auto cur = rank;
            cur.resize(2 * n, -1);
            k = 0;
            for (int i = 0; i < n; i++) rank[p[i]] = i and cur[p[i]] == cur[p[i - 1]] and cur[p[i] + m] == cur[p[i - 1] + m] ? rank[p[i - 1]] : k++;
        }

        for (int i = 0, c = 0; i < n; i++) {
            if (rank[i]) {
                if (c) c--;
                int j = p[rank[i] - 1];
                while (i + c < n && j + c < n && s[i + c] == s[j + c]) c++;
                height[rank[i]] = c;
            }
        }
    }
};

$$
lcp(suf_{i}, suf_{j}) = \min\limits_{k = rank_{i} + 1}^{rank_{j}} (height_{k})
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct Sparse_Table {
    int n;
    int logn;
    vector<int> log;
    vector<vector<int>> val;
    Sparse_Table(vector<int> v) {
        n = v.size();
        logn = log2(n);
        log.resize(n + 1);
        val.resize(n, vector<int>(logn + 1));
        for (int i = 2; i <= n; i++) {
            log[i] = log[i >> 1] + 1;
        }
        for (int i = 0; i < n; i++) {
            val[i][0] = v[i];
        }
        for (int j = 1; j <= logn; j++) {
            for (int i = 0; i + (1 << j) - 1 < n; i++) {
                val[i][j] = min(val[i][j - 1], val[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    int get(int l, int r) {
        if (l < 0 || r >= n) {
            return 0;
        }
        int k = log[r - l + 1];
        return min(val[l][k], val[r - (1 << k) + 1][k]);
    }
};

AcAutomaton

指针版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
template<int N = 26, int OFFSET = -'a'>
struct AcAutomaton {
    struct Node {
        int cnt;
        Node* prev;
        Node* next[N];
        vector<int> info;// 记录字符串 id
        vector<Node*> tree;// 记录 prev 来源，建树
        Node() {
            cnt = 0;
            prev = 0;
            for (int i = 0; i < N; i++) {
                next[i] = 0;
            }
        }
    };

    int n;
    Node* root;
    AcAutomaton(const vector<string>& vs) {
        n = vs.size();
        root = new Node();
        for (int i = 0; i < vs.size(); i++) {
            insert(vs[i], i);
        }
        build();
    }

    void insert(const string& s, int id) {
        Node* cur = root;
        for (auto& x : s) {
            if (cur->next[x + OFFSET] == 0) {
                cur->next[x + OFFSET] = new Node();
            }
            cur = cur->next[x + OFFSET];
        }
        cur->info.push_back(id);
    }

    void build() {
        queue<Node*> q;
        root->prev = root;
        for (int i = 0; i < N; i++) {
            if (root->next[i] != 0) {
                root->tree.push_back(root->next[i]);// build fail tree
                root->next[i]->prev = root;
                q.push(root->next[i]);
            } else {
                root->next[i] = root;
            }
        }

        while (!q.empty()) {
            auto cur = q.front();
            q.pop();
            for (int i = 0; i < N; i++) {
                if (cur->next[i] != 0) {
                    cur->prev->next[i]->tree.push_back(cur->next[i]);// build fail tree
                    cur->next[i]->prev = cur->prev->next[i];
                    q.push(cur->next[i]);
                } else {
                    cur->next[i] = cur->prev->next[i];
                }
            }
        }
    }

    vector<int> count(const string& s) {
        vector<int> res(n);
        auto cur = root;
        for (int i = 0; i < s.size(); i++) {
            cur = cur->next[s[i] + OFFSET];
            cur->cnt += 1;
        }

        auto dfs = [&](auto self, auto cur) -> void {
            for (auto& v : cur->tree) {
                self(self, v);
                cur->cnt += v->cnt;
            }

            for (auto& id : cur->info) {
                res[id] = cur->cnt;
            }
        };
        dfs(dfs, root);

        return res;
    }
};

数组版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
struct AcAutomaton {
    int N;
    int OFFSET;
    int n;
    int all;
    vector<int> fail, cnt;
    vector<vector<int>> ch;
    AcAutomaton(const vector<string>& vs, int _N = 26, int _OFFSET = -'a') {
        N = _N;
        OFFSET = _OFFSET;

        n = 0;
        all = 0;
        for (auto& x : vs) {
            n += x.size();
        }

        fail.resize(n + 1);
        cnt.resize(n + 1);
        ch.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            ch[i].resize(N);
        }

        for (auto& x : vs) {
            insert(x);
        }

        build();
    }

    void insert(const string& s) {
        int p = 0;
        for (auto& x : s) {
            if (ch[p][x + OFFSET] == 0) {
                ch[p][x + OFFSET] = ++all;
            }
            p = ch[p][x + OFFSET];
        }
        cnt[p] += 1;
    }

    void build() {
        queue<int> q;
        for (int i = 0; i < N; i++) {// #
            if (ch[0][i]) {
                q.push(ch[0][i]);
            }
        }

        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            for (int i = 0; i < N; i++) {
                if (ch[p][i] == 0) {
                    ch[p][i] = ch[fail[p]][i];
                } else {
                    fail[ch[p][i]] = ch[fail[p]][i];
                    cnt[ch[p][i]] += cnt[ch[fail[p]][i]];
                    q.push(ch[p][i]);
                }
            }
        }
    }
};

update: 2024/2/29

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
struct AcAutomaton {
    const int N;
    const int OFFSET;
    int n;
    int all;
    vector<int> fail, cnt;
    vector<vector<int>> ch;
    AcAutomaton(const vector<string>& vs, int _N = 26, int _OFFSET = -'a') : N(_N), OFFSET(_OFFSET) {
        n = 0;
        all = 0;
        for (auto& x : vs) {
            n += x.size();
        }

        fail.resize(n + 1);
        cnt.resize(n + 1);
        ch.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            ch[i].resize(N);
        }

        for (auto& x : vs) {
            insert(x);
        }

        build();
    }

    void insert(const string& s) {
        int p = 0;
        for (auto& x : s) {
            if (ch[p][x + OFFSET] == 0) {
                ch[p][x + OFFSET] = ++all;
            }
            p = ch[p][x + OFFSET];
        }
        cnt[p] += 1;
    }

    void build() {
        queue<int> q;
        for (int i = 0; i < N; i++) {
            if (ch[0][i]) {
                q.push(ch[0][i]);
            }
        }

        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            for (int c = 0; c < N; c++) {
                if (ch[p][c]) {
                    fail[ch[p][c]] = ch[fail[p]][c];
                    cnt[ch[p][c]] += cnt[ch[fail[p]][c]];
                    q.push(ch[p][c]);
                } else {
                    ch[p][c] = ch[fail[p]][c];
                }
            }
        }
    }
};

AcAutomaton + Fenwick 维护 fail tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
template<class T>
struct Fenwick {
    int N;
    vector<T> C, S;
    Fenwick(int n = 0) {
        resize(n);
    }

    void resize(int n) {
        N = n;
        C.resize(N);
        S.resize(N);
    }

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

    void add(int p, T k) {
        for (int i = p; i < N; i += lowbit(i)) {
            C[i] += k;
            S[i] += k * p;
        }
    }

    void update(int l, int r, T k) {
        add(l, + k);
        add(r + 1, -k);
    }

    T prefixsum(int p) {
        T Csum = 0;
        T Ssum = 0;
        for (int i = p; i > 0; i -= lowbit(i)) {
            Csum += C[i] * (p + 1);
            Ssum += S[i];
        }
        return Csum - Ssum;
    }

    T rangesum(int l, int r) {
        return prefixsum(r) - prefixsum(l - 1);
    }
};

struct AcAutomaton {
    const int N;
    const int OFFSET;
    int n;
    int all;
    vector<int> cnt;
    vector<int> fail;
    vector<vector<int>> ch;
    // other func
    int m; // vs size
    vector<int> id;// ith string -> the id of trie node
    vector<vector<int>> tree; // fail tree
    vector<int> dfn;// the dfn of fail tree node
    vector<int> siz;// ths size of subtree
    Fenwick<long long> f;// the cnt of fail tree node
    AcAutomaton(const vector<string>& vs, int _N = 26, int _OFFSET = -'a') : N(_N), OFFSET(_OFFSET) {
        n = 0;
        all = 0;
        m = vs.size();
        for (auto& x : vs) {
            n += x.size();
        }

        cnt.resize(n + 1);
        fail.resize(n + 1);
        ch.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            ch[i].resize(N);
        }

        id.resize(m);// m
        tree.resize(n + 1);
        dfn.resize(n + 1);
        siz.resize(n + 1, 1);// init with 1
        f.resize(n + 1);

        for (int i = 0; i < vs.size(); i++) {
            insert(vs[i], i);
        }
        
        build();
        all = 0;// reset all to 0
        dfs();
    } 

    void insert(const string& s, int i) {
        int p = 0;
        for (auto& x : s) {
            if (ch[p][x + OFFSET] == 0) {
                ch[p][x + OFFSET] = ++all;
            }
            p = ch[p][x + OFFSET];
        }
        cnt[p] += 1;
        id[i] = p;
    }

    void build() {
        queue<int> q;
        for (int i = 0; i < N; i++) {
            if (ch[0][i]) {
                tree[0].push_back(ch[0][i]);
                q.push(ch[0][i]);
            }
        }

        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            for (int i = 0; i < N; i++) {
                if (ch[p][i]) {
                    fail[ch[p][i]] = ch[fail[p]][i];
                    q.push(ch[p][i]);
                    cnt[ch[p][i]] += cnt[ch[fail[p]][i]];
                    tree[ch[fail[p]][i]].push_back(ch[p][i]);
                } else {
                    ch[p][i] = ch[fail[p]][i];
                }
            }
        }
    }

    void dfs(int u = 0) {
        dfn[u] = all++;// all++
        if (dfn[u]) {
            f.update(dfn[u], dfn[u], cnt[u]);
        }
        for (auto& v : tree[u]) {
            dfs(v);
            siz[u] += siz[v];
        }
    }

    void up(int i) {
        int l = dfn[id[i]];
        int r = dfn[id[i]] + siz[id[i]] - 1;
        f.update(l, r, + 1);
    }

    void dn(int i) {
        int l = dfn[id[i]];
        int r = dfn[id[i]] + siz[id[i]] - 1;
        f.update(l, r, - 1);
    }

    long long get(const string& s) {
        long long ans = 0;
        for (int i = 0, p = 0; i < s.size(); i++) {
            p = ch[p][s[i] + OFFSET];
            ans += f.rangesum(dfn[p], dfn[p]);
        }
        return ans;
    }
};

Suffix Automaton

$Tips$

  1. 本质不同的子串 $\sum (len(u) - len(link(u)))$
  2. $endpos$ 不是 $len$ ，分裂出的点有 $len$ 无 $endpos$
  3. $link \ tree$ 对子树求和可以得到 $endpos(s)$ 的大小，可以线段树合并计算子树的 $endpos$ （若在线计算， merge 需要可持久化开点）
  4. 以状态 $u$ 开始的子串数 $c_{u} = 1 + \sum c_{v}$ （在 $parent \ tree$ 上计算 ） 可用于求 $kth$ 子串，若要求本质不同 $|endpos(s)|$ 设置为 $1$ 即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
struct SAM {
    static constexpr int ALPHABET_SIZE = 26;
    static constexpr int N = 1e5 + 10;
    struct Node {
        int cnt;
        int len;
        int link;
        int endpos;
        int next[ALPHABET_SIZE];
        Node() : cnt{}, len{}, link{}, endpos{}, next{} {}
    };

    int cur;
    int all;
    Node node[N << 1];// 两倍 |S| 
    vector<int> tree[N << 1];

    SAM() {
        cur = 1;
        all = 1;
    }

    int newNode() {
        return ++all;
    }

    void extend(int c, int offset = -'a') {
        c += offset;
        int pre = cur;
        cur = newNode();
        node[cur].cnt = 1;
        node[cur].len = node[pre].len + 1;
        node[cur].endpos = node[pre].endpos + 1;// endpos
        while (pre && !node[pre].next[c]) {
            node[pre].next[c] = cur;
            pre = node[pre].link;
        }
        if (pre == 0) {
            node[cur].link = 1;
        } else {
            int pos = node[pre].next[c];
            if (node[pos].len == node[pre].len + 1) {
                node[cur].link = pos;
            } else {    
                int newpos = newNode();
                node[newpos].len = node[pre].len + 1;// 无 endpos
                node[newpos].link = node[pos].link;
                node[pos].link = newpos;
                node[cur].link = newpos;
                while (pre && node[pre].next[c] == pos) {
                    node[pre].next[c] = newpos;
                    pre = node[pre].link;
                }
                for (int i = 0; i < ALPHABET_SIZE; i++) {
                    node[newpos].next[i] = node[pos].next[i];
                }
            }
        }
    }
};

Extend Suffix Automaton

Off-line

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// 离线 ExSAM
struct ExSAM {
    static constexpr int N = 1e6 + 10;
    static constexpr int ALPHABET_SIZE = 26;
    struct Node {
        int len;
        int link;
        int next[ALPHABET_SIZE];
        Node() : len{}, link{}, next{} {}
    };

    int all;
    Node node[N << 1]; // |S| * 2
    ExSAM() : all(1) {}

    int newNode() {
        return ++all;
    }

    int insert(int lst, int c) {
        int cur = node[lst].next[c]; // 
        if (node[cur].len) return cur;
        node[cur].len = node[lst].len + 1;
        int pre = node[lst].link; // 和SAM 不一样
        while (pre && !node[pre].next[c]) {
            node[pre].next[c] = cur;
            pre = node[pre].link;
        }

        if (pre == 0) {
            node[cur].link = 1;
        } else {
            int pos = node[pre].next[c];
            if (node[pos].len == node[pre].len + 1) {
                node[cur].link = pos;
            } else {
                int newpos = newNode();
                node[newpos].len = node[pre].len + 1;
                node[newpos].link = node[pos].link;
                node[pos].link = newpos;
                node[cur].link = newpos;
                while (pre && node[pre].next[c] == pos) {
                    node[pre].next[c] = newpos;
                    pre = node[pre].link;
                }
                for (int i = 0; i < ALPHABET_SIZE; i++) {
                    if (node[node[pos].next[i]].len) { // 不会指向空
                        node[newpos].next[i] = node[pos].next[i];
                    } else {
                        node[newpos].next[i] = 0;
                    }
                }
            }
        }
        return cur;
    }

    // 一、建立字典树
    void insert(const string& s, int offset = -'a') {
        int p = 1;
        for (auto& x : s) {
            int c = x + offset;
            if (node[p].next[c] == 0) {
                node[p].next[c] = newNode();
            }
            p = node[p].next[c];
        }
    }

    // 二、字典树上拓扑建立SAM
    void build() {
        queue<pair<int, int>> q;
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            if (node[1].next[i]) {
                q.push({ i, 1 });
            }
        }

        while (!q.empty()) {
            auto [c, lst] = q.front();
            q.pop();
            int cur = insert(lst, c);
            for (int i = 0; i < ALPHABET_SIZE; i++) {
                if (node[cur].next[i]) {
                    q.push({ i, cur });
                }
            }
        }
    }
};

On-line

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// 在线 ExSAM
struct ExSAM {
    static constexpr int N = 1e6 + 10;
    static constexpr int ALPHABET_SIZE = 26;
    struct Node {
        int len;
        int link;
        int next[ALPHABET_SIZE];
        Node() : len{}, link{}, next{} {}
    };


    int all;
    Node node[N << 1]; // |S| * 2
    ExSAM() : all(1) {}

    int newNode() {
        return ++all;
    }

    int insert(int cur, int c) {
        if (node[cur].next[c]) {
            int pre = cur;
            int pos = node[pre].next[c];
            if (node[pos].len == node[pre].len + 1) {
                return pos;
            }
            int newpos = newNode();
            node[newpos].len = node[pre].len + 1;
            node[newpos].link = node[pos].link;
            node[pos].link = newpos;
            while (pre && node[pre].next[c] == pos) {
                node[pre].next[c] = newpos;
                pre = node[pre].link;
            }
            for (int i = 0; i < ALPHABET_SIZE; i++) {
                node[newpos].next[i] = node[pos].next[i];
            }
            return newpos;
        }
        // 下面和SAM一样
        int pre = cur;
        cur = newNode();
        node[cur].len = node[pre].len + 1;
        while (pre && !node[pre].next[c]) {
            node[pre].next[c] = cur;
            pre = node[pre].link;
        }
        if (pre == 0) {
            node[cur].link = 1;
        } else {
            int pos = node[pre].next[c];
            if (node[pos].len == node[pre].len + 1) {
                node[cur].link = pos;
            } else {    
                int newpos = newNode();
                node[newpos].len = node[pre].len + 1;
                node[newpos].link = node[pos].link;
                node[pos].link = newpos;
                node[cur].link = newpos;
                while (pre && node[pre].next[c] == pos) {
                    node[pre].next[c] = newpos;
                    pre = node[pre].link;
                }
                for (int i = 0; i < ALPHABET_SIZE; i++) {
                    node[newpos].next[i] = node[pos].next[i];
                }
            }
        }
        return cur;
    }

    void insert(const string& s, int offset = -'a') {
        int p = 1;
        for (auto& x : s) {
            int c = x + offset;
            p = insert(p, c);
        }
    }
};

$insert$ 中有一部分一样，递归算版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// 在线 ExSAM
struct ExSAM {
    static constexpr int N = 1e6 + 10;
    static constexpr int ALPHABET_SIZE = 26;
    struct Node {
        int len;
        int link;
        int next[ALPHABET_SIZE];
        Node() : len{}, link{}, next{} {}
    };


    int all;
    Node node[N << 1]; // |S| * 2
    ExSAM() : all(1) {}

    int newNode() {
        return ++all;
    }

    int insert(int cur, int c) {
        int pre = cur;
        if (node[cur].next[c]) {
            int pos = node[pre].next[c];
            if (node[pos].len == node[pre].len + 1) {
                return pos;
            }
            int newpos = newNode();
            node[newpos].len = node[pre].len + 1;
            node[newpos].link = node[pos].link;
            node[pos].link = newpos;
            while (pre && node[pre].next[c] == pos) {
                node[pre].next[c] = newpos;
                pre = node[pre].link;
            }
            for (int i = 0; i < ALPHABET_SIZE; i++) {
                node[newpos].next[i] = node[pos].next[i];
            }
            return newpos;
        }
        cur = newNode();
        node[cur].len = node[pre].len + 1;
        while (pre && !node[pre].next[c]) {
            node[pre].next[c] = cur;
            pre = node[pre].link;
        }
        if (pre == 0) {
            node[cur].link = 1;
        } else {
            node[cur].link = insert(pre, c);
        }
        return cur;
    }

    void insert(const string& s, int offset = -'a') {
        int p = 1;
        for (auto& x : s) {
            int c = x + offset;
            p = insert(p, c);
        }
    }
};

Palindromic Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
struct PAM {
    static constexpr int N = 3e5 + 10;
    static constexpr int ALPHABET_SIZE = 26;
    struct Node {
        int cnt;
        int len;
        int link;
        int next[ALPHABET_SIZE];
        Node() : len{}, link{}, cnt{}, next{} {}
    };
    int all;
    int svc;
    int suff;
    int vc[N];
    Node node[N];
    vector<int> tree[N];
    PAM() : all(-1), svc(-1), suff(0) { // root -> 1
        int pre = newNode();
        int cur = newNode();
        node[pre].len = 0;
        node[cur].len = -1;
        node[pre].link = cur;
        node[cur].link = pre;
    }

    int newNode() {
        return ++all;
    }

    int getLink(int x) {
        while (svc - node[x].len - 1 < 0 or vc[svc - node[x].len - 1] != vc[svc]) {
            x = node[x].link;
        }
        return x;
    }

    void extend(int c, int offset = -'a') {
        c += offset;
        vc[++svc] = c;
        int pre = getLink(suff);
        int cur = node[pre].next[c];
        if (cur == 0) {
            cur = newNode();
            node[cur].len = node[pre].len + 2;
            node[cur].link = node[getLink(node[pre].link)].next[c];
            node[pre].next[c] = cur; // next 要在 link 后 ！！！
        }
        node[cur].cnt += 1;
        suff = cur;
    }

    void dfs(int u = 1) {
        for (auto& v : tree[u]) {
            dfs(v);
            node[u].cnt += node[v].cnt;
        }
    }

    void build() {
        for (int v = 0; v <= all; v++) {
            if (v != 1) { // root = 1
                tree[node[v].link].push_back(v);
            }
        }
    }
};

Extend Palindromic Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
struct Pam {
    static constexpr int ALPHABET_SIZE = 26;
    struct Node {
        int cnt;
        int len;
        int link;
        int diff; // len(u) - len(link(u))
        int slink; // 跳 link 第一个 diff(u) != diff(v)
        int border;
        int next[ALPHABET_SIZE];
        Node() : cnt{}, len{}, link{}, diff{}, slink{}, border{}, next{} {}
    };

    int suff;
    string vc;
    vector<Node> node;

    Pam() {
        int pre = newNode();
        int cur = newNode();
        node[pre].len = 0;
        node[cur].len = -1;
        node[pre].link = cur;
        node[cur].link = pre;
        suff = 0;
    }

    int newNode() {
        node.emplace_back();
        return node.size() - 1;
    }

    int& len(int p) {
        return node[p].len;
    }

    int& link(int p) {
        return node[p].link;
    }

    int& diff(int p) {
        return node[p].diff;
    }

    int& slink(int p) {
        return node[p].slink;
    }

    int& border(int p) {
        return node[p].border;
    }

    int& next(int p, int c) {
        return node[p].next[c];
    }

    void extend(const string& s) {
        for (int i = 0; i < s.size(); i++) {
            extend(i, s[i]);
        }
        reset();
    }

    void reset() {
        suff = 0;
        vc.clear();
    }

    void extend(int p, char x, char offset = 'a') {
        int c = x - offset;
        vc += c;
        int pre = getLink(p, suff);
        int cur = next(pre, c);
        if (cur == 0) {
            cur = newNode();
            len(cur) = len(pre) + 2;
            link(cur) = next(getLink(p, link(pre)), c);
            next(pre, c) = cur;

            diff(cur) = len(cur) - len(link(cur));
            if (diff(cur) == diff(link(cur))) {
                slink(cur) = slink(link(cur));
            } else {
                slink(cur) = link(cur);
            }

            if (len(cur) - len(link(cur)) == len(border(link(cur)))) {
                border(cur) = border(link(cur));
            } else {
                border(cur) = cur;
            }
        }
        suff = cur;
    }

    int getLink(int p, int u) {
        while (p - len(u) - 1 < 0 or vc[p - len(u) - 1] != vc[p]) {
            u = link(u);
        }
        return u;
    }
};

trick

以第 $x$ 个字符结尾的回文串（后缀回文串）的长度会形成 $log(|S|)$ 段等差数列，如果要枚举所有后缀回文串，可考虑以下优化
$$
f_i = \sum f_j \quad if \quad (s[j + 1, i] 是回文)
$$
前置知识：

$diff[x] = len[x] = len[link[u]]$

$slink[u]$ 表示 $u$ 一直沿着 $link$ 向上跳到的第一个节点，使得 $diff[v] \neq diff[u]$

优化操作：

考虑每次算一个等差数列，这样只要算 $log|S|$ 次

设 $g[v]$ 表示其所在等差数列的 $f$ 和，且 $v$ 是等差数列中长度最长的节点

1
2
3
4
5
int x = v;
while (x != slink[v]) {
	g[v] += f[i - len[x]]; // i 表示此时枚举的下标
    x = link[x];
}

下面考虑如何更新 $g, f$

如下图， $g[x]$ 为橙色三个位置 $f$ 的和， $g[link[x]]$ 为蓝色两个位置的 $f$ 和，发现多了最后一个橙色 $f$ 的值，故 $g[x] = g[link[x]] + f[i - diff[x] - len[slink[x]]]$

当 $x$ 为其等差数列的最大长度时，不能加 $g[link[x]]$

pam_border

由此的 $g$ 的更新方式
$$
g[x] =
\begin{cases}
g[link[x]] + f[i - diff[x] - len[slink[x]]] & \text{if diff[x] $=$ diff[link[x]]} \
f[i - diff[x] - len[slink[x]]] & \text{if diff[x] $\neq$ diff[link[x]]}
\end{cases}
$$
然后跳 $log|S|$ 次 $slink$ 可得 $f$
$$
f_i = \sum\limits_{p = x}^{x > 1} g[p] \quad \text{$x$ 表示此时 $i$ 的节点位置, 每次更新 $x = slink[x]$}
$$

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> f(n + 1), g(n + 2);
f[0] = 1;
for (int i = 1; i <= n; i++) {
    pam.extend(i - 1, s[i - 1]);
    for (int p = pam.suff; p > 1; p = pam.slink(p)) {
        g[p] = f[i - pam.diff(p) - pam.len(pam.slink(p))]; // 必须是 = 覆盖之前的
        if (pam.diff(p) == pam.diff(pam.link(p))) {
            g[p] += g[pam.link(p)];
        }
        f[i] += g[p];
    }
}

另一个例子

最小回文分割

$f_{i} = min(f_{j} + 1) \quad \text{if $s_{j + 1, i}$ 是回文串}$

把 $+= \rightarrow min()$

若要回文长度为偶数，则再 $i$ 为偶数时计算 $f$

Sequence Automaton

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct SequenceAutomaton {
    static constexpr int ALPHABET_SIZE = 26;
    struct Node {
        int next[ALPHABET_SIZE];
        Node() : next{} {}
    };
    vector<Node> node;
    SequenceAutomaton(const string& s, int offset = -'a') {
        int n = s.size();
        node.resize(n + 1);
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < ALPHABET_SIZE; j++) {
                node[i].next[j] = node[i + 1].next[j];
            }
            node[i].next[s[i] + offset] = i + 1;
        }
    }

    bool count(const string& t, int offset = -'a') const {
        int p = 0;
        int i = 0;
        while (i < t.size() && node[p].next[t[i] + offset] != 0) {
            p = node[p].next[t[i] + offset];
            i++;
        }
        return i == t.size();
    }
};

unordered_map 版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct SequenceAutomaton {
    struct Node {
        unordered_map<int, int> next;
        Node() : next{} {}
    };
    vector<Node> node;
    SequenceAutomaton(const string& s) {
        int n = s.size();
        node.resize(n + 1);
        for (int i = n - 1; i >= 0; i--) {
            node[i].next = node[i + 1].next;
            node[i].next[s[i]] = i + 1;
        }
    }

    bool count(const string& t) const {
        int p = 0;
        int i = 0;
        while (i < t.size() && node[p].next.count(t[i])) {
            p = node[p].next.at(t[i]);
            i++;
        }
        return i == t.size();
    }
};

Minimal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// [0, n)
int minimal(auto s) {
    int n = s.size();
    int i = 0, j = 1, k = 0;
    while (k < n && i < n && j < n) {
        if (s[(i + k) % n] == s[(j + k) % n]) {
            k++;
        } else {
            s[(i + k) % n] > s[(j + k) % n] ? i += k + 1 : j += k + 1;
            if (i == j) j++;
            k = 0;
        }
    }
    return min(i, j);
}