DDOSvoid's Blog

CF 1276F Asterisk Substrings

发表于 分类于
本文字数： 4.3k 阅读时长 ≈ 4 分钟

题目描述

https://codeforces.com/contest/1276/problem/F

简要题意：给定一个字符串 $S$，令字符串 $T_i$ 为 $S[1\cdots i-1]++S[i+1\cdots n]$，其中 $$ 为一个不同于 $[a,z]$ 的字符，求 $\lbrace S,T_1,\cdots,T_n\rbrace$ 的本质不同的子串个数

$|S|\le 10^5$

Solution

容易发现我们需要统计五种字符串的数量，$S,S,S,,ST$，前四种较为容易，最后一种比较麻烦，我们首先考虑对于正反串各建一个 $SAM$，容易发现将结束位置为 $i-1$ 和 $i+1$ 的乘起来会算重，我们换一个做法，对于正串的每个节点统计有多少本质不同的 $T$，容易发现是一些树链的并，同时 $i-1$ 和 $i+1$ 是一一对应的，我们在正串的树上做启发式合并维护 $right$ 集合，同时维护 $right$ 集合所表示的树链的并

时间复杂度 $O(n\log^ 2n)$

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
// LUOGU_RID: 92052444
#include <iostream>
#include <set>
#include <cstring>
#include <vector>
#include <algorithm>
#define maxn 100010
#define Maxn 200010
#define ll long long
using namespace std;

int n;
char str[maxn];

struct SAM {
    struct node {
        int sz, L, l, nxt[26]; 
    } T[Maxn]; int f[Maxn], top, last, rt, pos[maxn];
    void init() {
        for (int i = 1; i <= top; ++i) {
            T[i].sz = T[i].L = T[i].l = f[i] = 0; 
            fill(T[i].nxt, T[i].nxt + 26, 0); 
        }
        rt = last = top = 1; 
        T[rt].L = T[rt].l = f[rt] = 0;
    }

    void extend(int ch, int k) {
        int np = ++top, p = last; last = np;
        T[np].L = T[p].L + 1; T[np].sz = 1; pos[k] = np;
        while (p && !T[p].nxt[ch]) T[p].nxt[ch] = np, p = f[p];
        if (!p) return f[np] = rt, void();
        int q = T[p].nxt[ch];
        if (T[q].L - 1 == T[p].L) f[np] = q;
        else {
            int nq = ++top; T[nq].L = T[p].L + 1; f[nq] = f[q];
            for (int i = 0; i < 26; ++i) T[nq].nxt[i] = T[q].nxt[i];
            while (p && T[p].nxt[ch] == q) T[p].nxt[ch] = nq, p = f[p];
            f[np] = f[q] = nq;
        } 
    }
    
    int tax[maxn], tp[Maxn];
    void rsort(int n) {
        for (int i = 1; i <= n; ++i) tax[i] = 0; 
        for (int i = 1; i <= top; ++i) ++tax[T[i].L];
        for (int i = 1; i <= n; ++i) tax[i] += tax[i - 1];
        for (int i = 1; i <= top; ++i) tp[tax[T[i].L]--] = i;
        for (int i = top, u = tp[i]; i > 1; u = tp[--i]) T[u].l = T[f[u]].L + 1;
    }

    vector<int> G[Maxn]; 
    
    int id[Maxn * 2], in[Maxn], cnt;
    void dfs(int u, int fa) {
        id[++cnt] = u; in[u] = cnt;
        for (auto v : G[u]) 
            dfs(v, u), id[++cnt] = u;
    }
    int st[Maxn * 2][21], Log[Maxn * 2];
    inline int st_min(int l, int r) { return in[l] < in[r] ? l : r; }
    void init_st(int n) { Log[0] = -1;
        for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
        for (int i = 1; i <= n; ++i) st[i][0] = id[i];
        for (int j = 1; j <= 20; ++j)
            for (int i = 1; i + (1 << j) - 1 <= n; ++i)
                st[i][j] = st_min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]); 
    }
    inline int get_lca(int l, int r) {
        l = in[l]; r = in[r]; if (l > r) swap(l, r);
        int k = Log[r - l + 1];
        return st_min(st[l][k], st[r - (1 << k) + 1][k]);
    }
} S, T, test;

struct cmps {
    bool operator () (const int &u, const int &v) const { return S.in[u] < S.in[v]; }
};
struct cmpt {
    bool operator () (const int &u, const int &v) const { return T.in[u] < T.in[v]; }
};

ll ans;
set<int, cmpt> s[Maxn]; int id[Maxn]; ll sum[Maxn];
void dfs(int u, int fa) {
    for (auto v : S.G[u]) {
        dfs(v, u);
        if (s[id[u]].size() < s[id[v]].size()) swap(id[u], id[v]);
        for (auto t : s[id[v]]) {
            auto it = s[id[u]].lower_bound(t);
            if (it != s[id[u]].end() && it != s[id[u]].begin()) {
                auto It = prev(it); 
                sum[id[u]] += T.T[T.get_lca(*it, *It)].L;
            }
            if (it != s[id[u]].end()) sum[id[u]] -= T.T[T.get_lca(*it, t)].L;
            if (it != s[id[u]].begin()) it = prev(it), sum[id[u]] -= T.T[T.get_lca(*it, t)].L;
            sum[id[u]] += T.T[t].L, s[id[u]].insert(t);
        }
    }
    if (u != S.rt) ans += sum[id[u]] * (S.T[u].L - S.T[u].l + 1); 
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> str + 1; n = strlen(str + 1);
    S.init(), T.init();
    for (int i = 1; i <= n; ++i) S.extend(str[i] - 'a', i);
    for (int i = n; i; --i) T.extend(str[i] - 'a', n - i + 1);
    S.rsort(n), T.rsort(n); 
    for (int i = 2; i <= S.top; ++i) ans += S.T[i].L - S.T[i].l + 1;
    for (int i = 2; i <= S.top; ++i) S.G[S.f[i]].push_back(i);
    for (int i = 2; i <= T.top; ++i) T.G[T.f[i]].push_back(i);

    test.init();
    for (int i = 2; i <= n; ++i) test.extend(str[i] - 'a', i);
    test.rsort(n - 1);
    for (int i = 2; i <= test.top; ++i) ans += test.T[i].L - test.T[i].l + 1;
    test.init();
    for (int i = n - 1; i; --i) test.extend(str[i] - 'a', i);
    test.rsort(n - 1);
    for (int i = 2; i <= test.top; ++i) ans += test.T[i].L - test.T[i].l + 1;
    
    S.dfs(S.rt, 0), S.init_st(2 * S.top - 1); T.dfs(T.rt, 0), T.init_st(2 * T.top - 1);
    
    for (int i = 1; i <= S.top; ++i) id[i] = i;
    for (int i = 2; i < n; ++i) {
        int x = S.pos[i - 1], y = T.pos[n - (i + 1) + 1];
        s[x].insert(y), sum[x] = T.T[y].L;
    } dfs(S.rt, 0); cout << ans + 2 << "\n";
    return 0;
}