「Codeforces 700E」Cool Slogans

题目链接:Codeforces 700E

Bomboslav 成立了一个品牌代理商,正在帮助公司创建商标和广告。就这个问题而言,公司的广告应该是其名称的非空子串。

有时,公司会对品牌进行重塑并改变广告。如果广告 $B$ 作为子串在广告 $A$ 中出现至少 $2$ 次(允许重叠),那么认为广告 $A$ 比 $B$ 更酷。

你得到了某个公司的名字 $w$,你的任务是帮助 Bomboslav 确定最长的广告序列 $s_1, s_2, \dots, s_k$ 满足任何一个广告都比上一个更酷。

数据范围:$1 \le \lvert w \rvert \le 2 \times 10 ^ 5$。


Solution

首先将问题化简:求出字符串序列 $s_i$ 的最长长度 $k$,满足如下约束条件:

  • 字符串 $s_i$ 是 $s_{i - 1}$ 的子串,且 $s_i$ 在 $s_{i - 1}$ 中作为子串出现了至少 $2$ 次。
  • $s_1 = w​$。

首先假设我们已经知道了如何判断字符串 $A​$ 是否在 $B​$ 中出现了 $2​$ 次,那么这个问题可以直接在 $\text{Parent}​$ 树上进行 $\text{DP}​$ 了。

考虑某个串 $A$ 在其非 $\text{Parent}$ 树上的子树中的节点对应的串 $B$ 中出现了 $2$ 次,那么 $B$ 一定是由 $A$ 子树内的某个串加上一个后缀得到的,这样子显然不优。因此只需要考虑在 $\text{Parent}$ 树上从上往下转移

我们对原串 $w$ 建立后缀自动机,如果字符串 $A$ 在 $B$ 中出现了 $2$ 次,那么在 $B$ 的所有 $endpos$ 位置的串 $B'$ 中都出现了 $2$ 次,因此对于字符串 $B$ 我们只需要对于 $\text{SAM}$ 上每个状态记录任意一个 $endpos$ 就行了。

但是对于字符串 $A$,我们需要维护其所有 $endpos$,以便与 $B$ 串进行匹配。我们可以用线段树维护每个状态的 $endpos$ 集合,从下往上采用线段树合并的方法对状态进行合并。

记状态 $i​$ 的任意一个 $endpos​$ 为 $pos(i)​$,状态 $i​$ 的最长后缀长度为 $len(i)​$。

考虑如何进行判断。对于状态 $i$,我们尝试判断其祖先状态 $j$ 是否在 $i$ 中出现了至少 $2$ 次。那么 $j$ 的 $endpos$ 集合一定要在 $[pos(i) - len(i) + len(j), pos(i)]$ 区间内出现至少 $2$ 次。

又因为 $j$ 一定是 $i$ 的真后缀,那么 $endpos$ 集合中一定有 $pos(i)$,故只需要判断 $j$ 的 $endpos$ 集合是否在区间 $[pos(i) - len(i) + len(j), pos(i) - 1]$ 内出现过。

考虑如何进行转移。定义 $f(i)$ 表示到状态 $i$ 的最大值。对于每个状态 $i$,我们需要枚举其在 $\text{Parent}$ 树上的所有祖先,如果某个状态 $j$ 合法,那么用 $f(j) + 1$ 更新 $f(i)$;如果不存在合法祖先状态,那么 $f(i)$ 直接继承 $f(link(i))$($link(i)$ 表示 $i$ 的后缀链接)的值。答案为 $\max\{f(i)\}$。

直接转移的复杂度是不对的。注意到从初始状态某个状态 $i$ 上的 $f$ 值是单调不降的。于是我们记录 $top(i)$ 表示 $i$ 到初始状态中(包括 $i$ 本身),所有 $f$ 值最大且 $len$ 最小的状态(其中 $len$ 最小是为了贪心地选择更小的,使得更有可能匹配成功)。那么直接判断 $top(link(i))$ 是否合法并更新 $f(i)$ 的值。

时间复杂度:$\mathcal O(n \log n)$。


Code

#include <cstdio>
#include <algorithm>

const int N = 2e5 + 5;

int n, rt[N << 1], bin[N], t[N << 1], f[N << 1], top[N << 1];
char s[N];

template <int MAX, int S>
struct SAM {
    static const int N = MAX << 1;
    int tot, lst, len[N], lnk[N], pos[N], nxt[N][S];
    SAM() {
        lnk[tot = lst = 0] = -1;
    }
    void insert(int x, int i) {
        int cur = ++tot;
        len[cur] = len[lst] + 1;
        pos[cur] = i;
        int p = lst;
        for (; ~p && !nxt[p][x]; p = lnk[p]) nxt[p][x] = cur;
        if (p == -1) {
            lnk[cur] = 0;
        } else {
            int q = nxt[p][x];
            if (len[q] == len[p] + 1) {
                lnk[cur] = q;
            } else {
                int c = ++tot;
                len[c] = len[p] + 1;
                lnk[c] = lnk[q];
                pos[c] = pos[q];
                std::copy(nxt[q], nxt[q] + S, nxt[c]);
                for (; ~p && nxt[p][x] == q; p = lnk[p]) nxt[p][x] = c;
                lnk[cur] = lnk[q] = c;
            }
        }
        lst = cur;
    }
};

template <int MAX>
struct SegmentTree {
    static const int N = MAX * 20;
    int tot, ls[N], rs[N];
    int merge(int p1, int p2) {
        if (!p1 || !p2) return p1 | p2;
        int p = ++tot;
        ls[p] = merge(ls[p1], ls[p2]);
        rs[p] = merge(rs[p1], rs[p2]);
        return p;
    }
    void modify(int &p, int l, int r, int x) {
        p = ++tot;
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (x <= mid) {
            modify(ls[p], l, mid, x);
        } else {
            modify(rs[p], mid + 1, r, x);
        }
    }
    bool query(int p, int l, int r, int x, int y) {
        if (!p) return false;
        if (x <= l && r <= y) return true;
        int mid = (l + r) >> 1;
        if (y <= mid) {
            return query(ls[p], l, mid, x, y);
        } else if (x > mid) {
            return query(rs[p], mid + 1, r, x, y);
        } else {
            return query(ls[p], l, mid, x, mid) | query(rs[p], mid + 1, r, mid + 1, y);
        }
    }
};

SAM<N, 26> S;
SegmentTree<N << 1> T;

int main() {
    scanf("%d%s", &n, s + 1);
    for (int i = 1; i <= n; i++) {
        S.insert(s[i] - 'a', i);
        T.modify(rt[S.lst], 1, n, i);
    }
    for (int i = 1; i <= S.tot; i++) bin[S.len[i]]++;
    for (int i = 1; i <= n; i++) bin[i] += bin[i - 1];
    for (int i = 1; i <= S.tot; i++) t[bin[S.len[i]]--] = i;
    for (int i = S.tot; i >= 1; i--) {
        int u = S.lnk[t[i]], v = t[i];
        rt[u] = T.merge(rt[u], rt[v]);
    }
    int ans = 1;
    for (int i = 1; i <= S.tot; i++) {
        int u = S.lnk[t[i]], v = t[i];
        if (u == 0) {
            f[v] = 1, top[v] = v;
            continue;
        }
        int g = top[u];
        if (T.query(rt[g], 1, n, S.pos[v] - S.len[v] + S.len[g], S.pos[v] - 1)) {
            f[v] = f[u] + 1, top[v] = v;
        } else {
            f[v] = f[u], top[v] = top[u];
        }
        ans = std::max(ans, f[v]);
    }
    printf("%d\n", ans);
    return 0;
}

发表评论