BZOJ 1396 识别子串 (后缀自动机+线段树)

题目大意：

给你一个字符串S，求关于每个位置x的识别串T的最短长度，T必须满足覆盖x，且T在S中仅出现一次

神题

以节点x为结尾的识别串，必须满足它在$parent$树的子树中只有一个$endpos$节点

若令$fa=pre_{x},L=dep_{fa},R=dep_{x}$

1.对于以$i\in[1,R-L]$为开头，以$R$为结尾的串，合法串的长度是$R-i+1$

如果在$S_{1...x}$串中不断删去开头的字符，删到串剩余长度为$dep_{fa}$时结束

上述过程在$parent$树里的表现为，从表示串$S_{1...x}$的节点$a$，删掉最后一个字符后，跳到了表示$S_{x-dep_{fa}+1...x}$的节点$b$

不必考虑$b$的$right$集合大小，因为$R$是递增的，如果$b$节点的串能作为识别串，$a$节点的答案一定不如$b$优秀

所以我们干脆只讨论不跳到$b$的情况就行了

那么$i\in[1,R-L]$为开头，$R$为结尾的的串一定都能作为$[1,R-L]$的识别串

2.对于以$i\in[R-L+1,R]$为开头，以$R$为结尾的串，合法串的长度是$R-L+1$

一样的道理，如果从$a$跳到了$b$，$b$节点的串可能不合法，但$a$节点的串一定合法

那么以$L$为开头，$R$为结尾的的串一定都能作为$[1,R-L+1]$的识别串

区间修改，单点查询，开两颗线段树维护一下就好

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 105000

 #define S1 (N1<<1)

 #define T1 (N1<<2)

 #define ll long long

 #define uint unsigned int

 #define rint register int

 #define il inline

 #define inf 0x3f3f3f3f

 #define idx(X) (X-'a')

 using namespace std;

 int gint()

 {

     int ret=,fh=;char c=getchar();

     while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

     while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}

     return ret*fh;

 }

 char str[N1];

 int len;

 struct Seg{

 int mi[S1<<];

 void pushdown(int rt){

     mi[rt<<]=min(mi[rt<<],mi[rt]);

     mi[rt<<|]=min(mi[rt<<|],mi[rt]);}

 void build(int l,int r,int rt)

 {

     mi[rt]=inf;

     if(l==r) return;

     int mid=(l+r)>>;

     build(l,mid,rt<<);

     build(mid+,r,rt<<|);

 }

 void update(int L,int R,int l,int r,int rt,int w)

 {

     if(L<=l&&r<=R) {mi[rt]=min(w,mi[rt]);return;}

     pushdown(rt);int mid=(l+r)>>;

     if(L<=mid) update(L,R,l,mid,rt<<,w);

     if(R>mid) update(L,R,mid+,r,rt<<|,w);

 }

 int query(int x,int l,int r,int rt)

 {

     if(l==r) return mi[rt];

     pushdown(rt);int mid=(l+r)>>;

     if(x<=mid) return query(x,l,mid,rt<<);

     else return query(x,mid+,r,rt<<|);

 }

 }s1,s2;

 namespace SAM{

 int trs[S1][],pre[S1],dep[S1],ed[S1],sz[S1],tot,la;

 void init(){tot=la=;}

 void reduct(){la=;}

 void insert(int c)

 {

     int p=la,np=++tot,q,nq;la=np;

     dep[np]=dep[p]+;ed[np]=;

     for(;p&&!trs[p][c];p=pre[p]) trs[p][c]=np;

     if(!p) {pre[np]=;return;}

     q=trs[p][c];

     if(dep[q]==dep[p]+) pre[np]=q;

     else{

         pre[nq=++tot]=pre[q];

         pre[q]=pre[np]=nq;

         dep[nq]=dep[p]+;

         memcpy(trs[nq],trs[q],sizeof(trs[q]));

         for(;p&&trs[p][c]==q;p=pre[p]) trs[p][c]=nq;

     }

 }

 int hs[S1],que[S1],ans[N1];

 void solve()

 {

     for(int i=;i<=tot;i++) hs[dep[i]]++;

     for(int i=;i<=len;i++) hs[i]+=hs[i-];

     for(int i=;i<=tot;i++) que[hs[dep[i]]--]=i;

     int x,fx;

     for(int i=tot-;i>;i--)

     {

         x=que[i];

         sz[x]+=(ed[x]?:);

         sz[pre[x]]+=sz[x];

     }

     s1.build(,tot,);

     s2.build(,tot,);

     for(int i=;i<=tot;i++)

     {

         x=que[i],fx=pre[x];

         if(sz[x]>) continue;

         if(dep[fx]>=) s1.update(dep[x]-dep[fx]+,dep[x],,tot,,dep[fx]+);

         if(dep[fx]+<=dep[x]) s2.update(,dep[x]-dep[fx],,tot,,dep[x]);

     }

     for(int i=;i<=len;i++)

     {

         ans[i]=min(s1.query(i,,tot,),s2.query(i,,tot,)-i+);

         printf("%d\n",ans[i]);

     }

 }

 };

 int main()

 {

     //freopen("t2.in","r",stdin);

     scanf("%s",str+);

     len=strlen(str+);

     SAM::init();

     for(int i=;i<=len;i++)

         SAM::insert(idx(str[i]));

     SAM::solve();

     return ;

 }

巴特西

BZOJ 1396 识别子串 (后缀自动机+线段树)

最新文章

热门文章