Skip to content
TechMind

字符串算法

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
28
29
string s;
int n = s.size();
s = ' ' + s;
vector<int> pi(n + 1); // 最长相等真前后缀的长度
int cnt = 0;
for (int i = 2; i <= n; i++)
{
    char b = s[i];
    while (cnt && s[cnt + 1] != b)
        cnt = pi[cnt];
    if (s[cnt + 1] == b)
        cnt++;
    pi[i] = cnt;
}

cnt = 0;
vector<int> ans;
for (int i = 1; i <= n; i++)
{
    while (cnt && s[i] != t[cnt + 1])
        cnt = pi[cnt];
    if (s[i] == t[cnt + 1])
        cnt++;
    if (cnt == m)
    {
        ans.push_back(i - m + 1);
        cnt = pi[cnt];
    }
}

z函数🧀

 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
string s, t; // z: t 与 t 的每一个后缀的 LCP 长度  p: b 与 a 的每一个后缀的 LCP 长度数组
int n = t.size(), m = s.size();
vector<int> z(n);
int l = 0, r = 0;
z[0] = n;
for (int i = 1; i < n; i++)
{
    if (i < r)
        z[i] = min(r - i, z[i - l]);
    while (i + z[i] < n && t[z[i]] == t[i + z[i]])
        z[i]++;
    if (i + z[i] > r)
        l = i, r = i + z[i];
}
vector<int> p(m);
while (p[0] < n && p[0] < m && s[p[0]] == t[p[0]])
    p[0]++;
l = 0, r = p[0];
for (int i = 1; i < m; i++)
{
    if (i < r)
        p[i] = min(r - i, z[i - l]);
    while (i + p[i] < m && t[p[i]] == s[i + p[i]])
        p[i]++;
    if (i + p[i] > r)
        l = i, r = i + p[i];
}

Manacher🧀

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int manacher(const string &S)
{
    s = "$#";
    for (auto &c : S)
    {
        s += c;
        s += '#';
    }
    int n = s.size() - 1;
    s += '^';
    vector<int> d(n + 1);
    int c = 0, r = 0;
    for (int i = 1; i <= n; i++)
    {
        if (i < r)
            d[i] = min(d[2 * c - i], r - i);
        while (s[i + d[i]] == s[i - d[i]])
            d[i]++;
        if (i + d[i] > r)
            c = i, r = i + d[i];
    }
    return ranges::max(d) - 1;
}

最小表示法🧀

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
string s;
int n = s.size();
s += s;
int i = 0, j = 1;
while (i < n && j < n)
{
    int k = 0;
    while (k < n && s[i + k] == s[j + k])
        k++;
    if (k == n)
        break;
    if (s[i + k] > s[j + k])
        i += k + 1;
    else
        j += k + 1;
    if (i == j)
        j++;
}

// 答案：s.substr(min(i, j), n)

AC自动机🧀

 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 ahocorasick
{
    static constexpr int sz = 26;
    struct node
    {
        int len;
        int link;
        bool end;
        array<int, sz> next;
        node() : len{0}, link{0}, end(0), next{} {}
    };
    vector<node> t;

    void init()
    {
        t.assign(2, node());
        t[0].next.fill(1);
        t[0].len = -1;
    }

    ahocorasick() { init(); };

    int newnode()
    {
        t.emplace_back();
        return t.size() - 1;
    }

    void add(const string &a)
    {
        int p = 1;
        for (auto c : a)
        {
            int x = c - 'a';
            if (t[p].next[x] == 0)
            {
                t[p].next[x] = newnode();
                t[t[p].next[x]].len = t[p].len + 1;
            }
            p = t[p].next[x];
        }
        t[p].end = 1;
    }

    void work()
    {
        queue<int> q;
        q.push(1);
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            for (int i = 0; i < sz; i++)
            {
                if (t[x].next[i] == 0)
                    t[x].next[i] = t[t[x].link].next[i];
                else
                {
                    t[t[x].next[i]].link = t[t[x].link].next[i];
                    t[t[x].next[i]].end |= t[t[t[x].next[i]].link].end;
                    q.push(t[x].next[i]);
                }
            }
        }
    }
};

后缀数组🧀

 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
// 板子内有idx调整，酌情修改
tuple<vector<int>, vector<int>, vector<int>> SA(string &s)
{
    int n = s.size(), m = 127, p = 0;
    s = ' ' + s;
    vector<int> sa(n * 2 + 5), rk(n * 2 + 5), height(n + 1), oldrk(n * 2 + 5), oldsa(n * 2 + 5), cnt(m + 1);

    for (int i = 1; i <= n; i++)
        cnt[rk[i] = s[i]]++;
    for (int i = 1; i <= m; i++)
        cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--)
        sa[cnt[rk[i]]--] = i;
    oldrk = rk;
    for (int i = 1; i <= n; i++)
        if (oldrk[sa[i]] == oldrk[sa[i - 1]])
            rk[sa[i]] = p;
        else
            rk[sa[i]] = ++p;

    for (int w = 1;; w <<= 1, m = p)
    {
        int cur = 0;
        for (int i = n - w + 1; i <= n; i++)
            oldsa[++cur] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > w)
                oldsa[++cur] = sa[i] - w;
        cnt.assign(max(130ll, m + 1), 0);
        for (int i = 1; i <= n; i++)
            cnt[rk[oldsa[i]]]++;
        for (int i = 1; i <= m; i++)
            cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--)
            sa[cnt[rk[oldsa[i]]]--] = oldsa[i];

        oldrk = rk;
        p = 0;
        for (int i = 1; i <= n; i++)
            if (oldrk[sa[i]] == oldrk[sa[i - 1]] && oldrk[sa[i] + w] == oldrk[sa[i - 1] + w])
                rk[sa[i]] = p;
            else
                rk[sa[i]] = ++p;
        if (p == n)
            break;
    }

    for (int i = 1, k = 0; i <= n; i++)
    {
        if (rk[i] == 0)
            continue;
        if (k)
            --k;
        while (s[i + k] == s[sa[rk[i] - 1] + k])
            ++k;
        height[rk[i]] = k;
    }

    return {sa, rk, height};
}

后缀自动机🧀

 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
struct SAM
{
    static constexpr int sz = 26;
    struct node
    {
        int len;
        int link;
        array<int, sz> next;
        node() : len{}, link{}, next{} {}
    };
    vector<node> t;

    SAM() { init(); }

    void init()
    {
        t.assign(2, node());
        t[0].next.fill(1);
        t[0].len = -1;
    }

    int newnode()
    {
        t.emplace_back();
        return t.size() - 1;
    }

    int extend(int p, int c)
    {
        if (t[p].next[c])
        {
            int q = t[p].next[c];
            if (t[q].len == t[p].len + 1)
                return q;
            int r = newnode();
            t[r].len = t[p].len + 1;
            t[r].link = t[q].link;
            t[r].next = t[q].next;
            t[q].link = r;
            while (t[p].next[c] == q)
            {
                t[p].next[c] = r;
                p = t[p].link;
            }
            return r;
        }
        int cur = newnode();
        t[cur].len = t[p].len + 1;
        while (!t[p].next[c])
        {
            t[p].next[c] = cur;
            p = t[p].link;
        }
        t[cur].link = extend(p, c);
        return cur;
    }

    int extend(int p, char c, char offset = 'a') { return extend(p, (int)c - offset); }
    int next(int p, int x) { return t[p].next[x]; }
    int next(int p, char c, char offset = 'a') { return next(p, (int)c - offset); }
    int link(int p) { return t[p].link; }
    int len(int p) { return t[p].len; }
    int size() { return t.size(); }
};