BZOJ1396 识别子串
传送门
题意描述
输入输出格式
输入格式：
一行,一个由小写字母组成的字符串$S$,长度不超过$10^5$。
输出格式：
$L$行,每行一个整数,第$i$行的数据表示关于$S$的第$i$个元素的最短识别子串有多长.
输入输出样例
输入样例#1：
agoodcookcooksgoodfood
输出样例#1：
1
2
3
3
2
2
3
3
2
2
3
3
2
1
2
3
3
2
1
2
3
4
分析
显然，可以用于更新答案的点一定是$Endpos$为$1$的点。
更新的值是什么？
根据$Parent$树的性质，一个点管辖的子串长中最短的子串长为父节点管辖的子串长中最长子串长$+1$，那么我们每次更新答案是就用$len _ {fa_i}+1$更新。
更新区间，想想父节点管辖的子串长为$len _ {fa_i}$，此节点管辖的子串长为$len_i$，那么不属于父节点管辖但属于此节点管辖的区间就为$[len_i - len _ {fa_i},len_i]$。
似乎是可以做了，但上述更新是不完全的。
举例说明bbbc 对于第三个位置答案应该是bc，但是c在更新的时候只用1更新了自己，而第三个b在更新的时候用3更新了[1,3]这个区间。
$\uparrow$ 例子来自clover_hxy的bzoj 1396: 识别子串 （后缀自动机+线段树）
为了应对这种情况，我们加一个更新。
即对于$[1,len_i - len _ {fa_i}-1]$段，可以用长度$len_i-i+1$更新。
$\uparrow$ 图来自Zig_zag的 bzoj1396 识别子串
先前在想，为什么$[1,len_i]$一定是识别子串，后来发现我们将子串$[1,len_i]$看作两部分，分别为$[1,len_i - len _ {fa_i}-1]$和$[len_i - len _ {fa_i},len_i]$，假设这个子串不是识别子串，即这个子串重复了，那么我们将它分为两部分以后，这两部分一定都重复了，而我们的$[len_i - len _ {fa_i},len_i]$这个子串一定不重复（$Endpos$为$1$），所以假设不成立，子串$[1,len_i]$是识别子串。
参考资料
Zig_zag的 bzoj1396 识别子串
clover_hxy的 bzoj 1396: 识别子串 （后缀自动机+线段树）
nianheng的 题解
代码
一次免调过？吓到自己了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
using namespace std;
template <typename T>inline T read()
{
register T sum=0;
register char cc=getchar();
int sym=1;
while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
if(cc=='-')sym=-1,cc=getchar();
sum=sum*10+cc-'0';
cc=getchar();
while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
return sym*sum;
}
template <typename T>inline T read(T &a)
{
a=read<T>();
return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
a=read(a);
read(b...);
}
struct Segment_Tree
{
struct Node
{
int val;
int tag;
Node()
{
val=tag=INF;
}
}node[maxn<<2];
void down(int k)
{
if(node[k].tag!=INF)
{
node[k<<1].val=min(node[k<<1].val,node[k].tag);
node[k<<1].tag=min(node[k<<1].tag,node[k].tag);
node[k<<1|1].val=min(node[k<<1|1].val,node[k].tag);
node[k<<1|1].tag=min(node[k<<1|1].tag,node[k].tag);
node[k].tag=INF;
}
}
void change(int k,int l,int r,int x,int y,int z)
{
if(l>=x&&r<=y)
{
node[k].val=min(node[k].val,z);
node[k].tag=min(node[k].tag,z);
return ;
}
down(k);
int mid=(l+r)>>1;
if(x<=mid)change(k<<1,l,mid,x,y,z);
if(y>mid)change(k<<1|1,mid+1,r,x,y,z);
node[k].val=min(node[k<<1].val,node[k<<1|1].val);
}
int query(int k,int l,int r,int x)
{
if(l==r)return node[k].val;
down(k);
int mid=(l+r)>>1;
if(x<=mid)return query(k<<1,l,mid,x);
return query(k<<1|1,mid+1,r,x);
}
}S,T;
int n,las=1,cnt=1,fa[maxn<<1],len[maxn<<1],siz[maxn<<1],ch[maxn<<1][26];
char str[maxn];
void add(int cc)
{
int p=las,np=las=++cnt;
len[np]=len[p]+1;
siz[np]=1;
for(;p&&!ch[p][cc];p=fa[p])ch[p][cc]=np;
if(!p)fa[np]=1;
else
{
int q=ch[p][cc];
if(len[q]==len[p]+1)fa[np]=q;
else
{
int nq=++cnt;
fa[nq]=fa[q];
len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[q]=fa[np]=nq;
for(;p&&ch[p][cc]==q;p=fa[p])ch[p][cc]=nq;
}
}
}
int main()
{
scanf("%s",str+1);
n=strlen(str+1);
for(int i=1;i<=n;i++)add(str[i]-'a');
for(int i=1;i<=cnt;i++)siz[fa[i]]=0;
for(int i=1;i<=cnt;i++)
{
if(siz[i]!=1)continue;
int l=len[i]-len[fa[i]],r=len[i];
S.change(1,1,n,l,r,len[fa[i]]+1);
if(l>1)T.change(1,1,n,1,l-1,r);
}
for(int i=1;i<=n;i++)
printf("%d\n",min(S.query(1,1,n,i),T.query(1,1,n,i)-i+1));
return 0;
}