NOI 2018 你的名字 后缀自动机 线段树合并

题解:过于复杂。。。有时间我再来修锅吧

#include <bits/stdc++.h>

const int MAXN = 3000000;

using namespace std;

int n,m,v,sz,d;
int ls[MAXN*20],rs[MAXN*20],mx[MAXN*20],rt[MAXN];
long long ans;
char s[MAXN];
vector<int>H[MAXN];

void update(int &o,int L,int R){
    if(!o) o = ++sz;
    if(L == R){
        mx[o] = v;
        return;
    }    
    int M = (L + R) >> 1;
    if(v <= M) update(ls[o],L,M);
    else update(rs[o],M+1,R);
    mx[o] = max(mx[ls[o]],mx[rs[o]]);
}

int merge(int x,int y){
    if(!x || !y) return x + y;
    int o = ++sz;
    ls[o] = merge(ls[x],ls[y]);
    rs[o] = merge(rs[x],rs[y]);
    mx[o] = max(mx[ls[o]],mx[rs[o]]);
    return o;
}

void query(int o,int L,int R,int qL,int qR){
    if(qL <= L && R <= qR){
         v = max(v,mx[o]);
        return;
    }
    int M = (L + R) >> 1;
    if(ls[o] && qL <= M) query(ls[o],L,M,qL,qR);
    if(rs[o] && M < qR) query(rs[o],M+1,R,qL,qR);
}

struct SAM{
    int cnt,root,las,cur;
    int ch[MAXN][26],fa[MAXN],len[MAXN],sum[MAXN],id[MAXN];

    void init(){
        for(int i = 1;i <= cnt;i++){
            len[i] = fa[i] = 0;
            for(int j = 0;j < 26;j++)
                ch[i][j] = 0;
        }
        cnt = 0;
        root = las = ++cnt;
    }

    void extend(int x){
        int p = las;
        int np = las = ++cnt;
        len[np] = len[p] + 1;
        for(;p && !ch[p][x] ;p = fa[p]) ch[p][x] = np;
        if(!p) fa[np] = root;
        else {
            int q = ch[p][x];
            if(len[q] == len[p] + 1) fa[np] = q;
            else {
                int nq = ++cnt;
                fa[nq] = fa[q];fa[q] = fa[np] = nq;
                len[nq] = len[p] + 1;
                memcpy(ch[nq],ch[q],sizeof(ch[nq]));
                for(;p && ch[p][x] == q;p = fa[p]) ch[p][x] = nq;
            }
        }
    }
    
    void Pre(){
        for(int i = 1;i <= cnt;i++) sum[len[i]]++;
        for(int i = 1;i <= cnt;i++)    sum[i] += sum[i-1];
        for(int i = 1;i <= cnt;i++)    id[sum[len[i]]--] = i;
        for(int i = cnt;i >= 1;i--) rt[fa[id[i]]] = merge(rt[fa[id[i]]],rt[id[i]]);
    }
    
    void Tran(int x,int L,int R){
        while(cur != root && !ch[cur][x]){ //直接往上跳
            cur = fa[cur];
            d = len[cur];
        }
        while(1){
            if(!ch[cur][x]){
                return;
            }
            v = 0;query(rt[ch[cur][x]],1,n,L+d,R);
            if(L + d <= v && v <= R){//匹配上了
                d++;cur = ch[cur][x];
                return;
            }
            else {//
                if(d != 0){
                    d--;
                    if(d <= len[fa[cur]] && cur != root) cur = fa[cur];
                }
                else return;
            }
        }
    }

    long long cal(){return len[las] - max(len[fa[las]],d);}

}S,S1;


int main(){ 
    //freopen("name.in","r",stdin);
    //freopen("name.out","w",stdout);
    scanf("%s",s+1);
    n = strlen(s+1);
    S.init();
    for(int i = 1;i <= n;i++){
        S.extend(s[i] - 'a');
        v = i;
        update(rt[S.las],1,n);
    }
    S.Pre();
    scanf("%d",&m);
    int L,R;
    while(m--){
        scanf("%s",s+1);
        scanf("%d %d",&L,&R);
        int len = strlen(s+1);
        S1.init();
        d = ans = 0;
        S.cur = S.root;
        for(int i = 1;i <= len;i++){
            S1.extend(s[i]-'a');
            S.Tran(s[i]-'a',L,R);
            ans += S1.cal();
        }
        printf("%lld\n",ans);
    }

    return 0;
}
Last modification:September 29th, 2019 at 08:28 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment