[BZOJ1396]识别子串

题目描述

求字符串每个位置被包含且出现只有一次的最短子串长度。

题解

\(SAM\) 部分很好想，关键是如何用线段树维护，我们假设当前位置为 \(r\)，对应的 \(np\) 节点为 \(x\)，则有左端点 \(l\ =\ r-maxlen(parent(x))\) 在区间 \([l,\ r]\) 内最小值为 \(maxlen(parent(x))+1\) 并且对于区间 \([1,\ l-1]\) 每个位置 \(i\) 来说，答案更新为 \(r-i+1\)，前面的信息很好维护，对于后面的位置来说，我们只需要做到单点查询，所以可以把 \(i\) 挪到外面，用另外一颗线段树维护即可

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+5;
int last = 1, tot = 1, ch[N][26], fa[N], len[N], pos[N], size[N];
int n, tax[N], p[N];
char s[N];
void insert(int c)
{
    int cur = ++tot, pre = last; last = tot;
    len[cur] = len[pre]+1; pos[len[cur]] = cur; size[cur] = 1;
    while(pre&&!ch[pre][c]) ch[pre][c] = cur, pre = fa[pre];
    if(!pre) return void(fa[cur] = 1);
    int x = ch[pre][c];
    if(len[pre]+1 == len[x]) return void(fa[cur] = x);
    int y = ++tot; len[y] = len[pre]+1; fa[y] = fa[x]; fa[x] = fa[cur] = y;
    memcpy(ch[y], ch[x], sizeof(ch[x]));
    while(pre&&ch[pre][c] == x) ch[pre][c] = y, pre = fa[pre];
}
struct Segment
{
    int val[N<<1];
    Segment() { memset(val, 0x3f, sizeof(val)); }
    void update(int x, int l, int r, int ql, int qr, int d)
    {
        if(ql > qr) return;
        if(ql <= l&&r <= qr) return void(val[x] = min(val[x], d));
        int mid = (l+r)>>1;
        if(ql <= mid) update(x<<1, l, mid, ql, qr, d);
        if(qr > mid) update(x<<1|1, mid+1, r, ql, qr, d);
    }
    int query(int x, int l, int r, int pos)
    {
        if(l == r) return val[x];
        int mid = (l+r)>>1;
        if(pos <= mid) return min(val[x], query(x<<1, l, mid, pos));
        else return min(val[x], query(x<<1|1, mid+1, r, pos));
    }
}a, b;
int main()
{
    scanf("%s", s+1); n = strlen(s+1);
    for(int i = 1; i <= n; ++i) insert(s[i]-'a');
    for(int i = 1; i <= tot; ++i) ++tax[len[i]];
    for(int i = 1; i <= tot; ++i) tax[i] += tax[i-1];
    for(int i = 1; i <= tot; ++i) p[tax[len[i]]--] = i;
    for(int i = tot; i; --i) size[fa[p[i]]] += size[p[i]];
    for(int i = 1; i <= n; ++i)
    {
        int x = pos[i]; if(size[x] > 1) continue;
        a.update(1, 1, n, i-len[fa[x]], i, len[fa[x]]+1);
        b.update(1, 1, n, 1, i-len[fa[x]]-1, i+1);
    }
    for(int i = 1; i <= n; ++i) printf("%d\n", min(a.query(1, 1, n, i), b.query(1, 1, n, i)-i));
    return 0;
}