DDOSvoid's Blog

2019-2020 Winter Petrozavodsk Camp, Day 8: Almost Algorithmic Contest B String Algorithm

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

题目描述

https://codeforces.com/gym/103261/problem/B

简要题意：给定一个长度为 $n$ 的字符串 $s$，现在对于 $k\in[1,n]$，求将 $s$ 分成 $m=\lfloor\frac{n}{k}\rfloor$ 段，每段长度为 $k$，第 $i$ 段的起点为 $(i-1)\times k+1$，定义 $f(k)=\sum_{1\le i <j\le m}[dist(p_i,p_j)\le 1]$，其中 $p_i$ 表示第 $i$ 段，$dist$ 表示两个串的汉明距离

$n\le 2\times 10^5$

Solution

我们考虑根号分治，将 $k$ 按照 $\sqrt n$ 进行分治

对于 $k<\sqrt n$，我们考虑 $O(n)$ 解决，我们计算每个串的每个位置变成 $?$ 的 $hash$ 值并进行计算，如果两个串恰有一个位置不同那么我们不会算重，如果两个串完全相同，那么我们会算 $k+1$ 次，稍微处理一下即可

对于 $k>\sqrt n$，我们直接枚举所有 $(i,j)$ 然后用后缀数组判一下 $lcp$ 和 $lcs$ 长度之和是否大于等于 $k-1$ 即可，枚举 $(i,j)$ 的复杂度为 $\frac{n^2}{k^2}$，$O(\sum_{k=\sqrt n}\frac{n^2}{k^2})=O(n\sqrt n)$

因为前半部分查找 $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
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
#include <iostream>
#include <cmath>
#include <cstring>
#include <unordered_map>
#include <vector>
#include <algorithm>
#define maxn 200010
#define ll long long
using namespace std;

struct SA {
    int tax[maxn], tp[maxn], sa[maxn], rk[maxn], M = 255, n; 
    void rsort() {
        for (int i = 0; i <= M; ++i) tax[i] = 0;
        for (int i = 1; i <= n; ++i) ++tax[rk[i]];
        for (int i = 1; i <= M; ++i) tax[i] += tax[i - 1];
        for (int i = n; i; --i) sa[tax[rk[tp[i]]]--] = tp[i];
    }
    
    int Log[maxn], st[maxn][21];
    void init_st() { Log[0] = -1;
        for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1, st[i][0] = H[i];
        for (int j = 1; j <= 20; ++j)
            for (int i = 1; i + (1 << j) - 1 <= n; ++i)
                st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
    }

    int query(int l, int r) {
        l = rk[l]; r = rk[r];
        if (l > r) swap(l, r); ++l;
        int k = Log[r - l + 1];
        return min(st[l][k], st[r - (1 << k) + 1][k]);
    }

    int H[maxn]; 
    void init(char *s) {
        if (n == 1) return sa[1] = rk[1] = 1, void(); int cnt = 1; n = strlen(s + 1); 
        for (int i = 1; i <= n; ++i) rk[i] = s[i], tp[i] = i; rsort();
        for (int k = 1; k < n; k *= 2) {
            if (cnt == n) break; M = cnt; cnt = 0;
            for (int i = n - k + 1; i <= n; ++i) tp[++cnt] = i;
            for (int i = 1; i <= n; ++i) if (sa[i] > k) tp[++cnt] = sa[i] - k;
            rsort(); swap(rk, tp); rk[sa[1]] = cnt = 1;
           
            for (int i = 2; i <= n; ++i) {
                if (tp[sa[i - 1]] != tp[sa[i]] || tp[sa[i - 1] + k] != tp[sa[i] + k]) ++cnt;
                rk[sa[i]] = cnt;
            }
        } int lcp = 0;
        for (int i = 1; i <= n; ++i) {
            if (lcp) --lcp;
            int j = sa[rk[i] - 1];
            while (s[j + lcp] == s[i + lcp]) ++lcp;
            H[rk[i]] = lcp;
        } init_st(); 
    }
} pres, sufs;

struct Hashtable {
    const int p = 20011203;
    struct node {
        ll v;
        int cnt, next; 
    } pool[maxn * 2]; vector<int> clr; int tab[20011203], top;

    void ins(ll v) {
        for (int i = tab[v % p]; i; i = pool[i].next) {
            node &u = pool[i];
            if (u.v == v) return ++u.cnt, void();
        }
        pool[++top] = { v, 1, tab[v % p] };
        tab[v % p] = top; clr.push_back(v % p); 
    }
    void init() {
        for (auto t : clr) tab[t] = 0;
        clr.clear(); top = 0; 
    }
    int query(ll v) {
        for (int i = tab[v % p]; i; i = pool[i].next) {
            node &u = pool[i];
            if (u.v == v) return u.cnt;
        } return 0; 
    }
} T;

struct Hash {
    const int base = 1331;
    const ll p = 212370440130137957;

    ll pow[maxn], h[maxn];

    inline ll mul(ll x, ll y) {
        return (x * y - (ll) ((long double) x / p * y) * p + p) % p;
    }
    inline ll add(ll x, ll y) { return (x += y) >= p ? x - p : x; } 

    void init(char *s) {
        int l = strlen(s + 1); 
        pow[0] = 1; for (int i = 1; i <= l; ++i) pow[i] = mul(pow[i - 1], base);
        for (int i = 1; i <= l; ++i)
            h[i] = add(s[i], mul(h[i - 1], base));
    }
    ll get(int l, int r) { return add(h[r], p - mul(h[l - 1], pow[r - l + 1])); }
} h;

int n;
char s[maxn];

ll solve_1(int k) {
    T.init(); ll ans = 0; 
    for (int i = 1; i <= n / k; ++i) {
        ll hash = h.get((i - 1) * k + 1, i * k), cnt = T.query(hash);
        ans += cnt; T.ins(hash);
        for (int j = (i - 1) * k + 1, l = k - 1; j <= i * k; ++j, --l) {
            ll v = h.add(hash, h.mul(255 - s[j], h.pow[l]));
            ans += T.query(v) - cnt; T.ins(v);
        }
    } return ans;
}

int solve_2(int k) {
    int ans = 0; 
    for (int i = 1; i <= n / k; ++i) 
        for (int j = i + 1; j <= n / k; ++j) {
            int l1 = (i - 1) * k + 1, r1 = i * k;
            int l2 = (j - 1) * k + 1, r2 = j * k;
            int suf = sufs.query(l1, l2), pre = pres.query(n - r1 + 1, n - r2 + 1);
            if (suf + pre >= k - 1) ++ans;
        }
    return ans;
}

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

    cin >> n >> s + 1; h.init(s); int sn = min(200, (int) sqrt(n));
    reverse(s + 1, s + n + 1); pres.init(s); reverse(s + 1, s + n + 1); sufs.init(s); 
    for (int k = 1; k <= n; ++k) {
        if (k <= sn) cout << solve_1(k) << " ";
        else cout << solve_2(k) << " ";
    }
    return 0;
}