bzoj 1396 识别子串

bzoj 1396 识别子串

​​ 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 考虑一个只i出现一次的串一定是一个前缀串

那么对答案的贡献分成两部分 一部分是len[x]-fa~len[x]的这部分贡献会是r-l+1因为只要多构前面一个字母就可以形成最小的 剩下一部分1~(len-fa)-1这部分 会和i~r构成答案 两棵线段树分开计数即可

#include#define lc (x<<1)#define rc (x<<1|1)using namespace std;const int N=1e5+10;const int inf=0x3f3f3f3f;int cnt=1,last=1,root=1,ch[N<<1][26],len[N<<1];char s[N];int fa[N<<1],size[N<<1],n;struct node{ int mn[N<<2]; inline void init(){memset(mn,0x3f,sizeof(mn));} inline void pushdown(int x){ if (mn[x]==inf) return; mn[lc]=min(mn[lc],mn[x]);mn[rc]=min(mn[rc],mn[x]);mn[x]=inf; } inline void modify(int x,int l,int r,int l1,int r1,int v){ if (l1<=l&&r1>=r){mn[x]=min(mn[x],v);return;} int mid=l+r>>1;pushdown(x); if (l1<=mid) modify(lc,l,mid,l1,r1,v); if (r1>mid) modify(rc,mid+1,r,l1,r1,v); } inline int query(int x,int l,int r,int p){ if (l==r) return mn[x]; int mid=l+r>>1;pushdown(x); if(p<=mid) return query(lc,l,mid,p); else return query(rc,mid+1,r,p); }}tree1,tree2;inline void insert1(int x){ int p=last,np=++cnt;len[np]=len[p]+1;size[np]=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[p]+1==len[q]) fa[np]=q;else{ int nq=++cnt;fa[nq]=fa[q];memcpy(ch[nq],ch[q],sizeof(ch[q])); fa[np]=fa[q]=nq;len[nq]=len[p]+1; for (;p&&ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } }last=np;}int main(){ freopen("bzoj1396.in","r",stdin); scanf("%s",s+1);n=strlen(s+1); for (int i=1;i<=n;++i) insert1(s[i]-'a'); for (int i=1;i<=cnt;++i) size[i]=1; for (int i=1;i<=cnt;++i) size[fa[i]]=0; tree1.init();tree2.init(); for (int i=1;i<=cnt;++i){ if (size[i]!=1) continue; int l=len[i]-len[fa[i]],r=len[i]; if(1<=l-1) tree1.modify(1,1,n,1,l-1,r+1); tree2.modify(1,1,n,l,r,r-l+1); } for (int i=1;i<=n;++i) printf("%d\n",min(tree1.query(1,1,n,i)-i,tree2.query(1,1,n,i))); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。