「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的每一位,最短的识别子串长度是多少,请你来帮助他。
    $\left|S\right|\le5\cdot10^5$


题目分析

识别子串加强版。

数据范围从$10^5$扩大了4倍,上后缀自动机会MLE。
就算用map和动态开点线段树也会MLE。(有人玄学开小数组过了,但不支持这种行为)

因为后缀自动机空间复杂度与字符集的大小有关,这时候后缀数组的优点就体现出来了,它的时空间复杂度与字符集无关。

考虑,构造好后缀数组后,相邻两个$sa$后缀存在$lcp$,其$lcp+1$一定是唯一出现的。
若$k=sa[i]$,对于$i\in[k,k+lcp]$,只有扩展到$lcp+1$才唯一,线段树更新。
对于$i\gt k+lcp$,能使其唯一的长度为$i-k+1$,与$i$有关,使用线段树$-k+1$,最后统一加上$i$即可。


代码

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
#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;
int sa[maxn],Rank[maxn],First[maxn],Second[maxn],Bucket[maxn],tmp[maxn],Height[maxn];
void Suffix_Array(int n,int* a) {
fill(Bucket,Bucket+n+1,0);
for(int i=1; i<=n; i++)Bucket[a[i]]++;
for(int i=1; i<=n; i++)Bucket[i]+=Bucket[i-1];
for(int i=1; i<=n; i++)Rank[i]=Bucket[a[i]-1]+1;
for(int t=1; t<=n; t*=2) {
for(int i=1; i<=n; i++) {
First[i]=Rank[i];
Second[i]=(i+t)>n?0:Rank[i+t];
}
fill(Bucket,Bucket+n+1,0);
for(int i=1; i<=n; i++)Bucket[Second[i]]++;
for(int i=1; i<=n; i++)Bucket[i]+=Bucket[i-1];
for(int i=1; i<=n; i++)tmp[n-(--Bucket[Second[i]])]=i;
fill(Bucket,Bucket+n+1,0);
for(int i=1; i<=n; i++)Bucket[First[i]]++;
for(int i=1; i<=n; i++)Bucket[i]+=Bucket[i-1];
for(int i=1; i<=n; i++)sa[Bucket[First[tmp[i]]]--]=tmp[i];
bool unique=true;
for(int j=1,last=0; j<=n; j++) {
int i=sa[j];
if(!last)Rank[i]=1;
else if(First[i]==First[last]&&Second[i]==Second[last])Rank[i]=Rank[last],unique=false;
else Rank[i]=Rank[last]+1;
last=i;
}
if(unique)break;
}
int k=0;
for(int i=1; i<=n; i++) {
if(Rank[i]==1)k=0;
else {
if(k>0)k--;
int j=sa[Rank[i]-1];
while(i+k<=n&&j+k<=n&&a[i+k]==a[j+k])k++;
}
Height[Rank[i]]=k;
}
}
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 n,a[maxn];
int main() {
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1; i<=n; i++)a[i]=s[i]-'a'+1;
Suffix_Array(n,a);
int root1=st1.build(1,n),root2=st2.build(1,n);
for(int i=1; i<=n; i++) {
int len=max(Height[i],Height[i+1]);
if(sa[i]+len<=n)st1.modify(1,sa[i],sa[i]+len,len+1);
st2.modify(1,sa[i]+len+1,n,1-sa[i]);
}
for(int i=1; i<=n; i++)printf("%d\n",min(st1.query(1,i),st2.query(1,i)+i));
return 0;
}
0%