JZOJ 2921.字符串识别

\(S\) 建 SAM,对 \(1 \le i \le |S|\),在 Parent Tree 上倍增求出 \(l_i = \max\{j \mid |{\rm endpos}(S_{j\dots i})| = 1\}\)

对于 \(1 \le i \le |S|\),若其存在,考虑其贡献。
显然对于 \([l_i,i]\) 内的位置,都会造成 \(i - l_i + 1\) 的贡献。将 \(i - l_i + 1\) 从大到小排序,使用线段树或珂朵莉树实现区间覆盖即可;
而对于 \(j \in [1,l_i)\),会造成 \(i - j + 1\) 的贡献。这部分的贡献将 \(l_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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;
const int N = 5e5;
const int LG = 20;
int n;
int ed[N + 5],ans[N + 5];
char s[N + 5];
struct note
{
int l,r;
inline bool operator>(const note &o) const
{
return r - l > o.r - o.l;
}
inline bool operator<(const note &o) const
{
return l < o.l;
}
} a[N + 5];
int seg[(N << 2) + 10];
inline void push(int p)
{
if(seg[p])
{
seg[ls] = seg[rs] = seg[p];
seg[p] = 0;
}
}
void update(int l,int r,int k,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
{
seg[p] = k;
return ;
}
push(p);
int mid = tl + tr >> 1;
l <= mid && (update(l,r,k,ls,tl,mid),1);
r > mid && (update(l,r,k,rs,mid + 1,tr),1);
}
int query(int x,int p,int tl,int tr)
{
if(tl == tr)
return seg[p] ? seg[p] : n;
push(p);
int mid = tl + tr >> 1;
return x <= mid ? query(x,ls,tl,mid) : query(x,rs,mid + 1,tr);
}
namespace SAM
{
struct node
{
int ch[26];
int fa,len;
} sam[(N << 1) + 5];
int las = 1,tot = 1;
int sz[(N << 1) + 5];
int c[N + 5],a[(N << 1) + 5];
int f[LG + 5][(N << 1) + 5];
inline void insert(int x)
{
int cur = las,p = ++tot;
sam[p].len = sam[cur].len + 1,sz[p] = 1;
for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
sam[cur].ch[x] = p;
if(!cur)
sam[p].fa = 1;
else
{
int q = sam[cur].ch[x];
if(sam[cur].len + 1 == sam[q].len)
sam[p].fa = q;
else
{
int nxt = ++tot;
sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
sam[cur].ch[x] = nxt;
}
}
las = p;
}
inline void build()
{
for(register int i = 1;i <= tot;++i)
++c[sam[i].len],f[0][i] = sam[i].fa;
for(register int i = 1;i <= LG;++i)
for(register int j = 1;j <= tot;++j)
f[i][j] = f[i - 1][f[i - 1][j]];
for(register int i = 1;i <= n;++i)
c[i] += c[i - 1];
for(register int i = tot;i > 1;--i)
a[c[sam[i].len]--] = i;
for(register int i = tot;i > 1;--i)
sz[sam[a[i]].fa] += sz[a[i]];
}
}
int main()
{
scanf("%s",s + 1),n = strlen(s + 1);
for(register int i = 1;i <= n;++i)
SAM::insert(s[i] - 'a'),ed[i] = SAM::las,a[i].r = i;
SAM::build();
for(register int i = 1,p;i <= n;++i)
{
p = ed[i];
for(register int j = LG;~j;--j)
if(SAM::f[j][p] && SAM::sz[SAM::f[j][p]] <= 1)
p = SAM::f[j][p];
a[i].l = SAM::sz[p] <= 1 ? i - SAM::sam[SAM::sam[p].fa].len : -0x3f3f3f3f;
}
sort(a + 1,a + n + 1,greater<note>());
for(register int i = 1;i <= n;++i)
update(a[i].l,a[i].r,a[i].r - a[i].l + 1,1,1,n);
sort(a + 1,a + n + 1);
for(register int i = n,j = n,mn = 0x3f3f3f3f;i;--i)
{
for(;i <= a[j].l && j;mn = min(mn,a[j--].r));
ans[i] = min(query(i,1,1,n),mn - i + 1);
}
for(register int i = 1;i <= n;++i)
printf("%d\n",ans[i]);
}