BZOJ1396: 识别子串

BZOJ1396: 识别子串

https://lydsy.com/JudgeOnline/problem.php?id=1396

分析:

• 出现一次即后缀链接树上叶子节点，且此时\(len_i\)等于在原串中出现位置的下标。
• 那么会被\(len_fa\)分成两段。
• 其中一段区间取min，一段区间取和这个位置的距离的min。
• 一个扫描线过去就行了。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <set>
using namespace std;
#define N 200050
char w[N];
int n,ch[N][26],fa[N],len[N],lst=1,cnt=1,sz[N],ke[N],ro[N],flg[N];
int ans[N],lb;
struct A {
    int x,r,flg;
}b[N<<1];
multiset<int>S;
bool cmp(const A &x,const A &y) {return x.x<y.x;}
void insert(int x,int id) {
    int p=lst,np=++cnt,q,nq;
    len[np]=len[p]+1; lst=np; flg[np]=id;
    for(;p&&!ch[p][x];p=fa[p]) ch[p][x]=np;
    if(!p) fa[np]=1;
    else {
        q=ch[p][x];
        if(len[q]==len[p]+1) fa[np]=q;
        else {
            nq=++cnt; len[nq]=len[p]+1;
            fa[nq]=fa[q];
            fa[q]=fa[np]=nq; flg[nq]=flg[q];
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            for(;p&&ch[p][x]==q;p=fa[p]) ch[p][x]=nq;
        }
    }
}
int main() {
    memset(ans,0x3f,sizeof(ans));
    scanf("%s",w+1);
    n=strlen(w+1);
    int i;
    for(i=1;i<=n;i++) insert(w[i]-'a',i);
    for(i=1;i<=cnt;i++) ke[len[i]]++;
    for(i=1;i<=cnt;i++) ke[i]+=ke[i-1];
    for(i=cnt;i;i--) ro[ke[len[i]]--]=i;
    for(i=1;i<=cnt;i++) sz[fa[i]]++;
    for(i=1;i<=cnt;i++) if(!sz[i]) {
        int x=fa[i];
        int mid=flg[i]-len[x];
        if(mid<=flg[i]) {
            b[++lb]=(A){mid,flg[i]-mid+1,1};
            b[++lb]=(A){flg[i]+1,flg[i]-mid+1,-1};
        }
    }
    sort(b+1,b+lb+1,cmp);
    int j=1;
    for(i=1;i<=n;i++) {
        for(;j<=lb&&b[j].x==i;j++) {
            if(b[j].flg==1) S.insert(b[j].r);
            else S.erase(S.find(b[j].r));
        }
        if(S.size()) {
            ans[i]=min(ans[i],*S.begin());
        }
    }
    S.clear();
    lb=0;
    for(i=1;i<=cnt;i++) if(!sz[i]) {
        int x=fa[i];
        int mid=flg[i]-len[x];
        if(mid>1) {
            b[++lb]=(A){1,flg[i],1};
            b[++lb]=(A){mid,flg[i],-1};
        }
    }
    sort(b+1,b+lb+1,cmp);
    j=1;
    for(i=1;i<=n;i++) {
        for(;j<=lb&&b[j].x==i;j++) {
            if(b[j].flg==1) S.insert(b[j].r);
            else S.erase(S.find(b[j].r));
        }
        if(S.size()) ans[i]=min(ans[i],*S.begin()-i+1);
    }
    for(i=1;i<=n;i++) printf("%d\n",ans[i]);
}

BZOJ1396: 识别子串

原文：https://www.cnblogs.com/suika/p/10205580.html