1396: 識別子串

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?312??Solved:?193
[Submit][Status][Discuss]

Description

Input

一行,一個由小寫字母組成的字符串S,長度不超過10^5

Output

L行,每行一個整數,第i行的數據表示關于S的第i個元素的最短識別子串有多長.

Sample Input

agoodcookcooksgoodfood

Sample Output

1
2
3
3
2
2
3
3
2
2
3
3
2
1
2
3
3
2
1
2
3
4

HINT

Source

Solution

BZOJ：1396

這題使用 后綴自動機+線段樹 的做法；

首先按照這道題的要求，所有的識別子串一定是$|Right|=1$的節點所代表的子串之一，問題在于統計最短。

這樣可以考慮再記錄每個$Right$集合的最后一個$endpos$，然后利用這個去考慮對原串每個位置的貢獻。

對于$[endpos-maxlen+1,endpos-minlen+1]$中的每個位置$x$，貢獻就是$endpos-x+1$；

理解起來就是對于$[endpos-maxlen+1,endpos-minlen+1]$中的每個子串都是單獨存在的，所以這個$Right$集合貢獻給他的答案就是這個點到$endpos$的長度。

對于$[endpos-minlen,endpos]$中的每個位置$x$，貢獻就是$minlen$；

理解起來就是對于$[endpos-minlen,endpos]$中的每個子串顯然是存在多個結束位置的，所以當前這個$Right$集合能夠貢獻給他的符合只出現一次且最短的，就是剛好跨過它的最小，即$minlen$。

這樣對于兩種情況，分別用線段樹去維護，至于第一種情況的$-x$是定值，所以拿到外面比較的時候再算進答案即可。

?

BZOJ2865

這道題和上道題完全一樣，不過數據范圍擴大了，需要卡內存...用上了map內存還是多10M...于是直接寫 后綴樹組+線段樹 的做法了。

和剛剛的想法類似。

考慮固定左端點$l$，對后面的影響。

容易發現，固定了$l$之后，對后面的答案，存在兩種影響。

設這樣兩種情況的分界點為$m$

對于第一種影響$[l,m]$貢獻的答案就是$lcp+1$，而第二種$[m+1,N]$的每個位置$x$貢獻答案就是$x-l+1$

所以這樣可以枚舉$sa_{i}$，對于$sa_{i}$它的$lcp+1$實際上就是與它相鄰的兩個后綴的$height_{max}+1$，那么分界點$m$恰好是$sa_{i}+lcp$.

理解起來就是對于它的$lcp$顯然是重復出現過的，那么這段的答案最短就是$lcp+1$，而對于這段之后的位置的影響，顯然就是 那個位置到當前位置$sa_{i}$的距離長度的串 最短。

用同樣的方法用兩棵線段樹維護.

?

Code

BZOJ1396

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; #define MAXN 100010 #define INF 0x7fffffff char S[MAXN]; int N; namespace SegmentTree{ #define lson now<<1 #define rson now<<1|1struct SgtNode{int l,r,minn,tag;};struct SegmentTree{SgtNode tree[MAXN<<2];inline void Update(int now) {tree[now].minn=min(tree[lson].minn,tree[rson].minn);}inline void Build(int now,int l,int r){tree[now].tag=tree[now].minn=INF;tree[now].l=l,tree[now].r=r;if (l==r) return;int mid=(l+r)>>1;Build(lson,l,mid); Build(rson,mid+1,r);}inline void Pushdown(int now){if (tree[now].l==tree[now].r || tree[now].tag==INF) return;int val=tree[now].tag; tree[now].tag=INF;tree[lson].minn=min(tree[lson].minn,val);tree[rson].minn=min(tree[rson].minn,val);tree[lson].tag=min(tree[lson].tag,val);tree[rson].tag=min(tree[rson].tag,val);}inline void Modify(int now,int L,int R,int val){if (L>R) return;int l=tree[now].l,r=tree[now].r;Pushdown(now);if (L<=l && R>=r) {tree[now].tag=min(tree[now].tag,val);tree[now].minn=min(tree[now].minn,val);return;}int mid=(l+r)>>1;if (L<=mid) Modify(lson,L,R,val);if (R>mid) Modify(rson,L,R,val);Update(now);}inline int Query(int now,int pos){int l=tree[now].l,r=tree[now].r;Pushdown(now);if (l==r) return tree[now].minn;int mid=(l+r)>>1;if (pos<=mid) return Query(lson,pos);else return Query(rson,pos);}}t1,t2; }using namespace SegmentTree;namespace SAM{int son[MAXN<<1][27],len[MAXN<<1],par[MAXN<<1],endpos[MAXN<<1],size[MAXN<<1];int last,root,sz;inline void init() {last=root=++sz;}inline void Extend(int c,int pos){int cur=++sz,p=last;len[cur]=len[p]+1; endpos[cur]=pos; size[cur]=1;while (p && !son[p][c]) son[p][c]=cur,p=par[p];if (!p) par[cur]=root;else {int q=son[p][c];if (len[p]+1==len[q]) par[cur]=q;else {int nq=++sz;memcpy(son[nq],son[q],sizeof(son[nq]));len[nq]=len[p]+1; par[nq]=par[q];while (p && son[p][c]==q) son[p][c]=nq,p=par[p];par[q]=par[cur]=nq; }}last=cur;}inline void Build() {init(); for (int i=1; i<=N; i++) Extend(S[i]-'a'+1,i);}int st[MAXN],id[MAXN<<1];inline void Prework(){for (int i=1; i<=sz; i++) st[len[i]]++;for (int i=1; i<=N; i++) st[i]+=st[i-1];for (int i=1; i<=sz; i++) id[st[len[i]]--]=i;for (int i=sz; i>=1; i--) {int x=id[i];size[par[x]]+=size[x];endpos[par[x]]=max(endpos[par[x]],endpos[x]);}}inline void Work(){for (int i=1; i<=sz; i++)if (size[i]==1) {int maxlen=len[i],minlen=len[par[i]]+1,end=endpos[i]; // printf("%d %d %d\n",end,maxlen,minlen);t1.Modify(1,end-maxlen+1,end-minlen+1,end+1);t2.Modify(1,end-minlen+1,end,minlen);}for (int i=1; i<=N; i++) {int x=t1.Query(1,i)-i,y=t2.Query(1,i);printf("%d\n",min(x,y));}} }using namespace SAM; int main() {scanf("%s",S+1); N=strlen(S+1);t1.Build(1,1,N),t2.Build(1,1,N);SAM::Build();SAM::Prework();SAM::Work();return 0; }

BZOJ2865

#include<iostream> #include<cmath> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; #define MAXN 500010 char S[MAXN]; int N; #define INF 0x3fffffff namespace SegmentTree{ #define lson now<<1 #define rson now<<1|1struct SgtNode{int l,r,minn,tag;};struct SegmentTree{SgtNode tree[MAXN<<2];inline void Update(int now) {tree[now].minn=min(tree[lson].minn,tree[rson].minn);}inline void Build(int now,int l,int r){tree[now].tag=tree[now].minn=INF;tree[now].l=l,tree[now].r=r;if (l==r) return;int mid=(l+r)>>1;Build(lson,l,mid); Build(rson,mid+1,r);}inline void Pushdown(int now){if (tree[now].l==tree[now].r || tree[now].tag==INF) return;int val=tree[now].tag; tree[now].tag=INF;tree[lson].minn=min(tree[lson].minn,val);tree[rson].minn=min(tree[rson].minn,val);tree[lson].tag=min(tree[lson].tag,val);tree[rson].tag=min(tree[rson].tag,val);}inline void Modify(int now,int L,int R,int val){if (L>R) return;int l=tree[now].l,r=tree[now].r;Pushdown(now);if (L<=l && R>=r) {tree[now].tag=min(tree[now].tag,val);tree[now].minn=min(tree[now].minn,val);return;}int mid=(l+r)>>1;if (L<=mid) Modify(lson,L,R,val);if (R>mid) Modify(rson,L,R,val);Update(now);}inline int Query(int now,int pos){int l=tree[now].l,r=tree[now].r;Pushdown(now);if (l==r) return tree[now].minn;int mid=(l+r)>>1;if (pos<=mid) return Query(lson,pos);else return Query(rson,pos);}}t1,t2; }using namespace SegmentTree;namespace SA{int r[MAXN],sa[MAXN],rank[MAXN],height[MAXN],st[MAXN],tx[MAXN],ty[MAXN];inline void Sort(int *x,int *y,int *sa,int L,int M){for (int i=0; i<=M; i++) st[i]=0;for (int i=0; i<L; i++) st[x[y[i]]]++;for (int i=1; i<=M; i++) st[i]+=st[i-1];for (int i=L-1; i>=0; i--) sa[--st[x[y[i]]]]=y[i]; }inline void DA(int *r,int *sa,int L,int M){int *x=tx,*y=ty,*t,i,j,p;for (int i=0; i<L; i++) x[i]=r[i],y[i]=i;Sort(x,y,sa,L,M);for (j=1,p=1; j<L && p<L; j<<=1,M=p-1) {for (p=0,i=L-j; i<L; i++) y[p++]=i;for (i=0; i<=L; i++) if (sa[i]>=j) y[p++]=sa[i]-j;Sort(x,y,sa,L,M);for (t=x,x=y,y=t,x[sa[0]]=0,i=1,p=1; i<L; i++)x[sa[i]]=y[sa[i]]==y[sa[i-1]] && y[sa[i]+j]==y[sa[i-1]+j]? p-1:p++;}}inline void Height(int *r,int *sa,int *rank,int *h,int L){h[1]=0;for (int i=1; i<=L; i++) rank[sa[i]]=i;for (int i=1,j,k=0; i<=L; h[rank[i++]]=k)for (k? k--:k=0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);} }using namespace SA;int main() {scanf("%s",S+1); N=strlen(S+1);for (int i=1; i<=N; i++) r[i]=S[i]-'a'+1;SA::DA(r,sa,N+1,27);SA::Height(r,sa,rank,height,N);// for (int i=1; i<=N; i++) printf("%d ",sa[i]); puts(""); // for (int i=1; i<=N; i++) printf("%d ",height[i]); puts("");t1.Build(1,1,N); t2.Build(1,1,N);for (int i=1; i<=N; i++) {int j=max(height[i],height[i+1])+1;if (j+sa[i]-1<=N) t1.Modify(1,sa[i],sa[i]+j-1,j);t2.Modify(1,sa[i]+j,N,1-sa[i]); // printf("%d %d %d %d\n",i,j,sa[i],j+sa[i]); }for (int i=1; i<=N; i++) {int x=t1.Query(1,i),y=t2.Query(1,i)+i;printf("%d\n",min(x,y));}return 0; }

?

自己斷斷續續想了好久才想到...真的是弱的沒救了....

轉載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/6284980.html

總結

以上是生活随笔為你收集整理的【BZOJ-13962865】识别子串字符串识别 后缀自动机/后缀树组 + 线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。