BZOJ1396: 识别子串

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1396

1396: 识别子串

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 240 Solved: 148
[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

据说因为SAM是一棵逆序的后缀树，那么每一位i的前缀(除了包含在别的前缀里面)所对应的节点一定是后缀树里的叶子节点。那么我们只要找到它的父亲节点，然后它的父亲节点对应的子串填上一位字符就是一个识别子串。具体膜拜这个博客：http://www.cnblogs.com/zig-zag/archive/2013/04/27/3047604.html，我还是太弱了。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #define inf 1<<30
 5 #define maxn 100005
 6 using namespace std;
 7 int n;
 8 char s[maxn];
 9 struct sam{
10     int last,tot,go[maxn*2][26],val[maxn*2],par[maxn*2];
11     bool v[maxn*2];
12     sam(){last=tot=1;}
13     int newnode(int x){val[++tot]=val[x]+1;return tot;}
14     void extend(int x){
15         int p=last,np=newnode(p);
16         while(p&&!go[p][x]) go[p][x]=np,p=par[p];
17         if(!p) par[np]=1;
18         else{
19             int q=go[p][x];
20             if(val[q]==val[p]+1) par[np]=q;
21             else{
22                 int nq=newnode(p);
23                 memcpy(go[nq],go[q],sizeof(go[q]));
24                 par[nq]=par[q]; par[q]=par[np]=nq;
25                 while(p&&go[p][x]==q) go[p][x]=nq,p=par[p];
26             }
27         }
28         last=np;
29     }
30 }sam;
31 struct T{
32     int mn[maxn*4];
33     T(){memset(mn,0x3f,sizeof(mn));}
34     void add(int z,int l,int r,int x,int y,int w){
35         if(l>y||r<x) return;
36         if(l>=x&&r<=y){mn[z]=min(mn[z],w);return;}
37         int mid=(l+r)>>1;
38         add(z*2,l,mid,x,y,w); add(z*2+1,mid+1,r,x,y,w);
39     }
40     int query(int z,int l,int r,int x){
41         if(l==r&&l==x) return mn[z];
42         int mid=(l+r)>>1;
43         if(x<=mid) return min(mn[z],query(z*2,l,mid,x));
44         else return min(mn[z],query(z*2+1,mid+1,r,x));
45     }
46 }f,t;
47 int main(){
48     scanf("%s",s+1); n=strlen(s+1);
49     for(int i=1;i<=n;i++) sam.extend(s[i]-'a');
50     for(int i=1;i<=sam.tot;i++) sam.v[sam.par[i]]=1;
51     for(int i=1;i<=sam.tot;i++)
52     if(!sam.v[i]){
53         int l=sam.val[i]-sam.val[sam.par[i]],r=sam.val[i];
54         f.add(1,1,n,l,r,r-l+1);
55         if(l>1) t.add(1,1,n,1,l-1,r);
56     }
57     for(int i=1;i<=n;i++) printf("%d
",min(f.query(1,1,n,i),t.query(1,1,n,i)-i+1));
58     return 0;
59 }

View Code