Sunglassman 的算法竞赛板子整理——字符串篇

发表于 分类于 ， ，

Sunglassman 的算法竞赛板子整理——字符串篇

字符集哈希

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
#include <bits/stdc++.h>
using namespace std;

constexpr int B = 3;

using ull = unsigned long long;
using HS = array<ull, B>;

mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

const HS operator-(const HS& a, const HS& b) {
    HS res;
    for (int i = 0; i < B; ++i) {
        res[i] = a[i] - b[i];
    }
    return res;
}
const HS operator+(const HS& a, const HS& b) {
    HS res;
    for (int i = 0; i < B; ++i) {
        res[i] = a[i] + b[i];
    }
    return res;
}

struct Hash {    
    static array<HS, 26> hs;
    static void init() {
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < B; ++j) {
                hs[i][j] = rnd();
            }
        }
    }

    vector<HS> H;
    int n;
    Hash(const string& s) {
        n = s.length() - 1;
        H.resize(n + 1);
        for (int j = 1; j <= n; ++j) {
            H[j] = H[j - 1] + hs[s[j] - 'a'];
        }
    }
    HS get(int l, int len) {
        return H[l + len - 1] - H[l - 1];
    }
};

array<HS, 26> Hash::hs;

滚动哈希

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
#include <bits/stdc++.h>
using namespace std;

constexpr int B = 3;

using ull = unsigned long long;
using HS = array<ull, B>;

mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

const HS operator-(const HS& a, const HS& b) {
    HS res;
    for (int i = 0; i < B; ++i) {
        res[i] = a[i] - b[i];
    }
    return res;
}
const HS operator+(const HS& a, const HS& b) {
    HS res;
    for (int i = 0; i < B; ++i) {
        res[i] = a[i] + b[i];
    }
    return res;
}
const HS operator*(const HS& a, const HS& b) {
    HS res;
    for (int i = 0; i < B; ++i) {
        res[i] = a[i] * b[i];
    }
    return res;
}
const HS operator+(const HS& a, ull b) {
    HS res;
    for (int i = 0; i < B; ++i) {
        res[i] = a[i] + b;
    }
    return res;
}

struct RollingHash {
    static HS bs;
    static vector<HS> P;
    static void init() {
        for (int i = 0; i < B; ++i) bs[i] = rnd() | 1;
    }
    static void expand(int len) {
        if (P.empty()) {
            HS E;
            for (int i = 0; i < B; ++i) E[i] = 1;
            P.push_back(E);
        }
        while ((int)P.size() <= len) P.push_back(P.back() * bs);
    }

    vector<HS> H;
    int n;
    RollingHash(const string& s) {
        n = s.length() - 1;
        H.resize(n + 1);
        expand(n);
        for (int i = 1; i <= n; ++i) {
            P[i] = P[i - 1] * bs;
            H[i] = H[i - 1] * bs + s[i];
        }
    }
    HS get(int l, int len) {
        return H[l + len - 1] - H[l - 1] * P[len];
    }
};

HS RollingHash::bs;
vector<HS> RollingHash::P;

KMP

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
#include <bits/stdc++.h>
using namespace std;

constexpr int M = 1e6 + 10;

int ne[M];

int main() {
    string ss, tar; cin >> ss >> tar;
    int n = ss.size(), m = tar.size();
    ss = '1' + ss, tar = '0' + tar;
    for (int i = 2, j = 0; i <= m; ++i) {
        while (j && tar[i] != tar[j + 1]) j = ne[j];
        if (tar[i] == tar[j + 1]) ++j;
        ne[i] = j;
    }
    vector<int> ans;
    for (int i = 1, j = 0; i <= n; ++i) {
        while (j && ss[i] != tar[j + 1]) j = ne[j];
        if (ss[i] == tar[j + 1]) ++j;
        if (j == m) ans.push_back(i - m + 1), j = ne[j];
    }
    for (auto t : ans) cout << t << '\n';
    for (int i = 1; i <= m; ++i) cout << ne[i] << ' ';
    cout << '\n';
    return 0;
}

P5357 【模板】AC 自动机

题目描述

给你一个文本串 $S$ 和 $n$ 个模式串 $T_{1 \sim n}$，请你分别求出每个模式串 $T_i$ 在 $S$ 中出现的次数。

输入格式

第一行包含一个正整数 $n$ 表示模式串的个数。

接下来 $n$ 行，第 $i$ 行包含一个由小写英文字母构成的非空字符串 $T_i$。

最后一行包含一个由小写英文字母构成的非空字符串 $S$。

数据不保证任意两个模式串不相同。

输出格式

输出包含 $n$ 行，其中第 $i$ 行包含一个非负整数表示 $T_i$ 在 $S$ 中出现的次数。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
5
a
bb
aa
abaa
abaaa
abaaabaa

输出 #1

1
2
3
4
5
6
0
3
2
1

说明/提示

对于 $100 %$ 的数据，$1 \le n \le 2 \times {10}^5$，$T_{1 \sim n}$ 的长度总和不超过 $2 \times {10}^5$，$S$ 的长度不超过 $2 \times {10}^6$。

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
#include <bits/stdc++.h>
using namespace std;

constexpr int M = 2e5 + 10;

namespace AC {

int tr[M][26], fail[M], ed[M], sum[M], cnt = 0;
vector<int> adj[M];

int insert(string ss) {
    int u = 0;
    for (char ch : ss) {
        int c = ch - 'a';
        if (!tr[u][c]) tr[u][c] = ++cnt;
        u = tr[u][c];
    }
    return u;
}

void bfs() {
    queue<int> q;
    for (int i = 0; i < 26; ++i) {
        if (tr[0][i]) q.push(tr[0][i]);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < 26; ++i) {
            if (tr[u][i]) {
                fail[tr[u][i]] = tr[fail[u]][i];
                q.push(tr[u][i]);
            }
            else {
                tr[u][i] = tr[fail[u]][i];
            }
        }
    }
}

void dfs(int u) {
    for (auto v : adj[u]) {
        dfs(v);
        sum[u] += sum[v];
    }
}

void work(vector<string>& ss, string tar) {
    for (int i = 0; i < ss.size(); ++i) {
        ed[i] = insert(ss[i]);
    }
    bfs();
    for (int i = 1; i <= cnt; ++i) {
        adj[fail[i]].push_back(i);
    }
    int u = 0;
    for (auto ch : tar) {
        int c = ch - 'a';
        u = tr[u][c];
        sum[u]++;
    }
    dfs(0);
}

}

int main() {
    int n; cin >> n;
    vector<string> ss(n);
    for (int i = 0; i < n; ++i) {
        cin >> ss[i];
    }
    string tar; cin >> tar;
    AC::work(ss, tar);
    for (int i = 0; i < n; ++i) {
        cout << AC::sum[AC::ed[i]] << '\n';
    }

    return 0;
}