「bzoj1396」识别子串 - 后缀自动机+线段树 | Bill Yang's Blog

「bzoj1396」识别子串 - 后缀自动机+线段树

题目大意

    XX在进行字符串研究的时候,遇到了一个十分棘手的问题。
    在这个问题中,给定一个字符串$S$,与一个整数$K$,定义$S$的子串$T=S(i,j)$是关于第$K$位的识别子串,满足以下两个条件:
    $1.i\le K\le j$。
    $2.$子串$T$只在$S$中出现过一次。
    例如,$S=banana$,$K=5$,则关于第$K$位的识别子串有nanaananananananbananbanana
    现在,给定$S$,XX希望知道对于S的每一位,最短的识别子串长度是多少,请你来帮助他。


题目分析

显然,所有的识别子串都在SAM的$\left|end-pos(x)\right|=1$的结点$x$上。
其中每个结点$x$包含长度为$[Min(x),Max(x)]$的串。
不妨维护$end$-$pos$集合的最后位置$end$。
故对于$i\in[end-Max(x)+1,end-Min(x)+1]$,$i$位置的识别子串长度当前最短为$end-i+1$,因为所有串都唯一出现。
对于$i\in(end-Min(x)+1,end]$,$i$位置的识别子串长度当前最短为$Min(x)$,因为串$i\rightarrow end$不一定唯一出现,需要补全到$end-Min(x)+1$才能保证唯一出现。

对于第二种情况,直接用线段树维护。
对于第一种情况,注意到$end-i+1$,唯一有影响的是$i$,故线段树维护$end+1$,最后统一减去$i$即可。

当然也可以使用李超树$O(n\log^2 n)$ 或 堆+排序+单调队列$O(n\log n)$。


代码

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=500005,maxc=26;
struct SuffixAutomaton {
int cnt,root,last;
int next[maxn*2],Max[maxn*2],end_size[maxn*2],end_pos[maxn*2];
int child[maxn*2][maxc],Bucket[maxn*2],top[maxn*2];
SuffixAutomaton() {
cnt=0;
root=last=newnode(0);
}
int newnode(int val) {
cnt++;
next[cnt]=end_pos[cnt]=0;
Max[cnt]=val;
memset(child[cnt],0,sizeof(child[cnt]));
return cnt;
}
void insert(int data,int pos) {
int p=last,u=newnode(Max[last]+1);
last=u;
end_size[u]=1;
end_pos[u]=pos;
for(; p&&!child[p][data]; p=next[p])child[p][data]=u;
if(!p)next[u]=root;
else {
int old=child[p][data];
if(Max[old]==Max[p]+1)next[u]=old;
else {
int New=newnode(Max[p]+1);
copy(child[old],child[old]+maxc,child[New]);
next[New]=next[old];
next[u]=next[old]=New;
for(; child[p][data]==old; p=next[p])child[p][data]=New;
}
}
}
void build(string s) {
int cnt=0;
for(auto x:s)insert(x-'a',++cnt);
}
void topsort() {
for(int i=1; i<=cnt; i++)Bucket[Max[i]]++;
for(int i=1; i<=cnt; i++)Bucket[i]+=Bucket[i-1];
for(int i=1; i<=cnt; i++)top[Bucket[Max[i]]--]=i;
}
void get_end_pos() {
topsort();
for(int i=cnt; i>=1; i--) {
int x=top[i];
end_size[next[x]]+=end_size[x];
end_pos[next[x]]=max(end_pos[next[x]],end_pos[x]);
}
}
} sam;
struct Segment_Tree {
struct Tree {
int ls,rs;
int left,right;
int min,lazy;
Tree(int l=0,int r=0):left(l),right(r) {
ls=rs=0;
min=lazy=INT_MAX/2;
}
} tree[maxn<<1];
int size;
#define ls tree[index].ls
#define rs tree[index].rs
int build(int Left,int Right) {
int index=++size;
tree[index]=Tree(Left,Right);
if(Left==Right)return index;
int mid=(Left+Right)>>1;
ls=build(Left,mid);
rs=build(mid+1,Right);
return index;
}
void push_up(int index) {
tree[index].min=min(tree[ls].min,tree[rs].min);
}
void modify(int index,int val) {
tree[index].min=min(tree[index].min,val);
tree[index].lazy=min(tree[index].lazy,val);
}
void push_down(int index) {
if(tree[index].left==tree[index].right||tree[index].lazy==INT_MAX/2)return;
modify(ls,tree[index].lazy);
modify(rs,tree[index].lazy);
tree[index].lazy=INT_MAX/2;
}
void modify(int index,int Left,int Right,int val) {
if(Left>tree[index].right||Right<tree[index].left)return;
if(Left<=tree[index].left&&Right>=tree[index].right) {
modify(index,val);
return;
}
push_down(index);
modify(ls,Left,Right,val);
modify(rs,Left,Right,val);
push_up(index);
}
int query(int index,int target) {
if(target>tree[index].right||target<tree[index].left)return INT_MAX/2;
if(tree[index].left==tree[index].right)return tree[index].min;
push_down(index);
return min(query(ls,target),query(rs,target));
}
} st1,st2;
char s[maxn];
int main() {
scanf("%s",s);
int n=strlen(s);
sam.build(s);
sam.get_end_pos();
int root1=st1.build(1,n),root2=st2.build(1,n);
for(int i=1; i<=sam.cnt; i++)
if(sam.end_size[i]==1) {
int Max=sam.Max[i],Min=sam.Max[sam.next[i]]+1,end=sam.end_pos[i];
st1.modify(root1,end-Max+1,end-Min+1,end+1);
st2.modify(root2,end-Min+1,end,Min);
}
for(int i=1; i<=n; i++)printf("%d\n",min(st1.query(1,i)-i,st2.query(1,i)));
return 0;
}
0%