题解 CF700E 【Cool Slogans】

xht · 2020-03-15 02:44:37 · 题解

CF700E Cool Slogans

题意

• 给定一个长度为 n 的字符串 s。
• 你要构造一个最长的字符串序列 t_{1\dots k}，满足：
  1. 对于 i \in [1,k]，t_i 为 s 的子串。
  2. 对于 i \in [2,k]，t_i 在 t_{i-1} 中出现了至少两次。

题解

对字符串建 SAM，用可持久化线段树合并求出每个节点的 \operatorname{endpos} 集合。

在 \operatorname{parent} 树上从根向下 dp，设 f_i 表示到节点 i 时的最大值。

如果一个父节点的子串在子节点的子串中出现了至少两次，则转移时 f 加一，否则不变。

考虑如何判断是否出现了至少两次，设此时的子节点为 x，父节点为 pa_x。

找到 x 对应的 \operatorname{endpos} 中的任意一个位置 pos，则 pos 处 pa_x 的子串一定出现了一次。

那么另一次只要在 [pos - \operatorname{len}(x) + \operatorname{len}(pa_x), pos - 1] 中有出现就行了。

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

代码

const int N = 2e5 + 7;
struct T {
    int l, r;
} t[N<<6|1];
int rt[N<<1], f[N<<1], g[N<<1], tot, ans = 1;

int insert(int l, int r, int x) {
    int p = ++tot;
    if (l == r) return p;
    int mid = (l + r) >> 1;
    if (x <= mid) t[p].l = insert(l, mid, x);
    else t[p].r = insert(mid + 1, r, x);
    return p;
}

int merge(int p, int q) {
    if (!p || !q) return p | q;
    int o = ++tot;
    t[o].l = merge(t[p].l, t[q].l);
    t[o].r = merge(t[p].r, t[q].r);
    return o;
}

bool ask(int p, int l, int r, int L, int R) {
    if (!p) return 0;
    if (L <= l && R >= r) return 1;
    int mid = (l + r) >> 1;
    if (L <= mid && ask(t[p].l, l, mid, L, R)) return 1;
    if (R > mid && ask(t[p].r, mid + 1, r, L, R)) return 1;
    return 0;
}

struct SAM {
    int n, l, ch[N<<1][26], len[N<<1], pa[N<<1], t;
    char s[N];
    int pos[N<<1];
    inline void init() { pa[0] = -1; }
    inline void add(int c, int o) {
        int w = ++t, p = l;
        len[w] = len[l] + 1, pos[w] = o;
        while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
        if (!~p) return pa[l=w] = 0, void();
        int q = ch[p][c];
        if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
        int k = ++t;
        pa[k] = pa[q], pos[k] = pos[q], memcpy(ch[k], ch[q], sizeof(ch[k]));
        len[k] = len[p] + 1, pa[w] = pa[q] = k;
        while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
        l = w;
    }
    inline void build() {
        init();
        for (int i = 1; i <= n; i++) add(s[i] - 'a', i);
    }
    int b[N<<1], c[N];
    inline void sort() {
        for (int i = 1; i <= t; i++) ++c[len[i]];
        for (int i = 1; i <= n; i++) c[i] += c[i-1];
        for (int i = 1; i <= t; i++) b[c[len[i]]--] = i;
    }
    inline void work() {
        for (int i = 1, p = 0; i <= n; i++)
            p = ch[p][s[i]-'a'], rt[p] = insert(1, n, i);
        for (int i = t; i; i--)
            rt[pa[b[i]]] = merge(rt[pa[b[i]]], rt[b[i]]);
        for (int i = 1; i <= t; i++) {
            int x = b[i];
            if (!pa[x]) {
                f[x] = 1, g[x] = x;
                continue;
            }
            if (ask(rt[g[pa[x]]], 1, n, pos[x] - len[x] + len[g[pa[x]]], pos[x] - 1))
                f[x] = f[pa[x]] + 1, g[x] = x;
            else f[x] = f[pa[x]], g[x] = g[pa[x]];
            ans = max(ans, f[x]);
        }
    }
} sam;

int main() {
    rd(sam.n), rds(sam.s, sam.n), sam.build();
    sam.sort(), sam.work(), print(ans);
    return 0;
}