BZOJ1396 识别子串

题外话

好久没发东西了
最近感觉在退役的边缘疯狂试探

题意

自己看

题解

SAM+线段树

发现只出现一次说明在 SAM 中对应节点的 right 集合大小为 1 (叶子)

那么对于某个符合条件的节点,它能够表示的字符串为 $[1,mx_i-mx_{fa}]$ (不难发现它的结束位置就是 $mx_i$ )

设 $r=mx_i,l=mx_i-mx_{fa}$

那么对于左端点在 $[1,mx_i-mx_{fa}]$ 右端点为 $mx_i$ 的字符串 $[i,mx_i]$,他们的识别子串可以取到长度为 $mx_i-i+1(r-i+1)$ ,对于左端点为 $[mx_i-mx_{fa},mx_i]$ 的子串,它们的识别子串长度可以取到 $mx_{fa}+1 (r-l+1)$

然后用一个线段树维护 $r-l+1$ ,发现 $r-i+1$ 不好区间修改,所以另一颗线段树维护 $r+1$ 最后算答案的时候再对每个位置 $i$ 在第二棵线段树的值上减去 $i$ 就行了

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

#define reg register
#define MAX_N 100007
#define rep(i, l, r) for(int i = l; i <= r; ++i)
typedef long long ll;

template <typename _T>
inline bool read (_T& x) {
    x = 0;
    _T y = 1;
    char c = getchar();
    while ((c < '0' || '9' < c) && c != EOF) {
        if (c == '-') y = -1;
        c = getchar();
    }
    if (c == EOF) return false;
    while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
    x *= y;
    return true;
}

struct SAM {
    int root, last, siz;

    struct node {
        int fa, mx;
        int go[26];

        node (int l = 0) : fa(0), mx(l) { memset(go, 0, sizeof(go)); }
    }t[MAX_N << 1];

    inline void init () { root = last = siz = 1; t[1] = node(0); }

    inline void insert (int c) {
        int p = last, np = ++siz;
        t[np] = node(t[p].mx + 1);
        while (p && !t[p].go[c]) t[p].go[c] = np, p = t[p].fa;
        if (!p) t[np].fa = root;
        else {
            int q = t[p].go[c];
            if (t[q].mx == t[p].mx + 1) {
                t[np].fa = q;
            } else {
                int nq = ++siz;
                t[nq] = node(t[p].mx + 1);
                t[nq].fa = t[q].fa;
                memcpy(t[nq].go, t[q].go, sizeof(t[q].go));
                t[q].fa = t[np].fa = nq;
                while (p && t[p].go[c] == q) t[p].go[c] = nq, p = t[p].fa;
            }
        }
        last = np;
    }
}sam;

struct segTree {
    int mn[MAX_N << 2];

    inline void init (int N) { rep (i, 1, N << 2) mn[i] = 1e8; }

    inline void add (int x, int v) { mn[x] = std::min(mn[x], v); }

    inline void pushdown (int x) {
        if (mn[x] < 1e8) {
            add(x << 1, mn[x]);
            add(x << 1 | 1, mn[x]);
            mn[x] = 1e8;
        }
    }

    void modify (int x, int l, int r, int pl, int pr, int v) {
        if (pl > pr) return;
        if (pl <= l && r <= pr) return add(x, v), void();
        pushdown(x);
        int mid = l + r >> 1;
        if (pl <= mid) modify(x << 1, l, mid, pl, pr, v);
        if (mid < pr) modify(x << 1 | 1, mid + 1, r, pl, pr, v);
    }
}t1, t2;

int N;
char s[MAX_N];
bool vis[MAX_N << 1];

void getans (int x, int l, int r) {
    if (l == r) return printf("%d\n", std::min(t1.mn[x] - l, t2.mn[x])), void();
    t1.pushdown(x), t2.pushdown(x);
    int mid = l + r >> 1;
    getans(x << 1, l, mid);
    getans(x << 1 | 1, mid + 1, r);
}

int main () {
#ifndef ONLINE_JUDGE
    freopen ("in", "r", stdin);
#endif
    sam.init();
    scanf("%s", s + 1);
    N = strlen(s + 1);
    t1.init(N), t2.init(N);
    rep (i, 1, N) sam.insert(s[i] - 'a');
    rep (i, 1, sam.siz) vis[sam.t[i].fa] = true;
    rep (i, 2, sam.siz) if (!vis[i]) {
        int r = sam.t[i].mx, l = r - sam.t[sam.t[i].fa].mx;
        t1.modify(1, 1, N, 1, l - 1, r + 1);
        t2.modify(1, 1, N, l, r, r - l + 1);
    }
    getans(1, 1, N);
    return 0;
}

sys_con

OIer,常规 / 竞赛都渣得不行