BZOJ 2865 문자열 인식

접미사 자동 동기 + 선분 트 리
최종 적 으로 점 i 를 포함 하 는 한 번 만 나타 나 는 하위 문자열 의 길 이 를 고려 합 니 다.이 문자열 은 [l, r] 라 고 기억 하 세 요.
l < i < r: 즉, i 는 좌우 점 에 닿 지 않 습 니 다. 이러한 상황 에 대해 SAM 에서 한 번 나타 난 모든 꼬치 를 폭력 적 으로 찾 아 선분 트 리 로 답 을 업데이트 할 수 있 습 니 다.
l = i ≤ r: r 를 오른쪽 단점 으로 한 번 나타 나 는 가장 짧 은 꼬치 는 [l ', r] 이 고 분명히 l ≤ l' 이 있어 야 한다.그래서 한 번 나 오 는 모든 꼬치 를 폭력 적 으로 찾 아 r 로 [1, l - 1] 의 답 을 업데이트 할 수 있다.
l ≤ i = r: r 를 오른쪽 단점 으로 한 번 나타 나 는 가장 짧 은 꼬치 는 [l ', r] 이 고 분명히 l = l' 이 있어 야 하기 때문에 이런 상황 은 첫 번 째 와 같다.
그래서 선분 나무 두 그루 만 필요 합 니 다.이 문 제 는 SAM 을 사용 하면 카드 메모리 가 됩 니 다. SAM 의 크기 는 적당히 줄 이면 됩 니 다.

#include
#include
#define N 500003
#define M 850003
#define A 26
#define cmin(u,v) (u)>(v)?(u)=(v):0
using namespace std;
namespace runzhe2000
{
    const int INF = 1<<29;
    int n, sum[N], ans[N];
    char s[N];

    struct SAM
    {
        SAM *next[A], *fail;
        int len, right;
    }mem[M], *tot, *null, *root, *last, *pos[M];
    SAM* newnode(int len)
    {
        SAM *p = ++tot;
        *p = *null; p->len = len;
        return p;
    }
    void init()
    {
        null = tot = mem;
        for(int i = 0; i < A; i++) null->next[i] = null;
        null->fail = null; null->len = null->right = 0;
        last = root = newnode(0);
    }
    void insert(int v)
    {
        SAM *np = newnode(last->len + 1), *p = last; last = np; np->right = 1;
        for(; p != null && p -> next[v] == null; p = p->fail) p->next[v] = np;
        if(p == null) np->fail = root;
        else
        {
            SAM *q = p->next[v];
            if(p->len + 1 == q->len) np->fail = q;
            else
            {
                SAM *nq = newnode(0);
                *nq = *q; nq->len = p->len + 1;
                nq -> right = 0; // attention
                q->fail = np->fail = nq;
                for(; p != null && p->next[v] == q; p = p->fail) p->next[v] = nq;
            }
        }
    }

    struct segment_tree
    {
        struct node {int val;}t[N*5];
        void build(int x, int l, int r)
        {
            t[x].val = INF; if(l == r)return;
            int mid = (l+r)>>1;
            build(x<<1,l,mid); build(x<<1|1,mid+1,r);
        }
        void modi(int x, int l, int r, int ql, int qr, int val)
        {
            if(ql <= l && r <= qr) {cmin(t[x].val, val); return;}
            int mid = (l+r)>>1;
            if(ql <= mid) modi(x<<1,l,mid,ql,qr,val);
            if(mid < qr) modi(x<<1|1,mid+1,r,ql,qr,val);
        }
        void pushall(int x, int l, int r, int val)
        {
            cmin(val, t[x].val);
            if(l == r){cmin(ans[l], val); return;}
            int mid = (l+r)>>1;
            pushall(x<<1,l,mid,val);
            pushall(x<<1|1,mid+1,r,val);
        }
    }t1,t2;

    void main()
    {
        scanf("%s",s+1);
        n = strlen(s+1);
        init();
        for(int i = 1; i <= n; i++)
            insert(s[i] - 'a');
        t1.build(1,1,n); 
        t2.build(1,1,n);
        int cnt = tot - mem;
        for(SAM *i = tot; i != mem; i--) sum[i->len]++;
        for(int i = 1; i <= n; i++) sum[i] += sum[i-1];
        for(SAM *i = tot; i != mem; i--) pos[sum[i->len]--] = i;
        for(int i = cnt; i; i--) 
        {
            SAM *p = pos[i]; if(p == root) continue;
            p->fail->right += p->right;
            if(p->right == 1)
            {
                int l = p->len - p->fail->len , r = p->len;
                if(1 <= l-1)t1.modi(1,1,n,1,l-1,r);
                t2.modi(1,1,n,l,r,r-l+1);
            }
        }
        memset(ans,63,sizeof(ans));
        t1.pushall(1,1,n,INF);
        for(int i = 1; i <= n; i++) ans[i] = ans[i] - i + 1;
        t2.pushall(1,1,n,INF);
        for(int i = 1; i <= n; i++) printf("%d
",ans[i]);
    }
}
int main()
{
    runzhe2000::main();
}