SPOJ - NSUBSTR - Substrings

Posted on In Disqus:

题目

http://www.spoj.com/problems/NSUBSTR/

题意

给一个字符串 \(s\)，对于所有不超过该字符串的长度 \(l(1\le l \le |s|)\)，求所有长度为 \(l\) 的子串中，出现次数的最大值。

题解

  • 对于所有子串，都能在 SAM 中找到一个对应的状态 \(s\)，这个状态也对应了一个在原串中的出现位置以及次数。（也就是 \(right\) 集合）
  • 利用拓扑序求逆序后缀树中每个结点（状态）对应的出现次数 \(cnt[u]\)，其中关键点自带有 1 的次数（因为本身就是后缀），然后累加儿子的次数。
  • 用 \(cnt[u]\) 更新 \(ans[len[u]]\)，然后从大往小用 \(ans[i]\) 更新 \(ans[i-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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 3E5 + 100;

namespace SAM {
    const int M = maxn << 1;
    int t[M][26], len[M] = {-1}, fa[M], sz = 2, last = 1, cnt[M];
    void ins(int ch) {
        int p = last, np = last = sz++;
        cnt[np] = 1;
        len[np] = len[p] + 1;
        for (; p && !t[p][ch]; p = fa[p])
            t[p][ch] = np;
        if (!p) { fa[np] = 1; return; }
        int q = t[p][ch];
        if (len[p] + 1 == len[q]) fa[np] = q;
        else {
            int nq = sz++; len[nq] = len[p] + 1;
            memcpy(t[nq], t[q], sizeof t[0]);
            fa[nq] = fa[q];
            fa[np] = fa[q] = nq;
            for (; t[p][ch] == q; p = fa[p])
                t[p][ch] = nq;
        }
    }
}

using namespace SAM;
int in[maxn << 1], f[maxn];
char s[maxn];

int main() {
    scanf("%s", s);
    FOR (i, 0, strlen(s)) ins(s[i] - 'a');
    FOR (i, 2, sz) ++in[fa[i]];
    queue<int> q;
    FOR (i, 1, sz) if (!in[i]) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cnt[fa[u]] += cnt[u];
        f[len[u]] = max(f[len[u]], cnt[u]);
        if (!--in[fa[u]]) q.push(fa[u]);
    }
    FORD (i, strlen(s), 0) f[i - 1] = max(f[i - 1], f[i]);
    FOR (i, 1, strlen(s) + 1) printf("%d\n", f[i]);
}