题意
给定一个大串 $S$ 以及 $q$ 次询问, 每次询问给定一个串 $T$ 和区间 $[l,r]$, 求 $T$ 中有多少本质不同的子串不是 $S[l:r]$ 的子串.
$|S|\le 5\times 10^5,q\le 10^5,\sum|T|\le10^6$.
题解
普通的码农字符串题…
获得成就: $40\texttt{min}(2400\texttt{s})$ 内打完 $3.9\texttt{kB}$ 的代码(然而并没有打完就A…还是太菜了…)
感觉考场上如果T1T2没打满的话写个 $68$ 分沙雕SAM暴力(询问区间都是原串的 $17$ 个测试点)就可以跑路了…分高好写还不用调…
个人的大体思路是: 因为求本质不同子串个数是容易的, 所以先补集转化为求 $T$ 的所有本质不同的子串中是 $S[l:r]$ 的串的个数.
按照套路我们维护一个类似扫描线的东西, 用SAM对 $T$ 的所有下标 $i$ 求出以 $i$ 为右端点且是 $S[l:r]$ 的子串的最长子串长度. 按照SAM的套路, 这部分的计算就是直接用 $T$ 在 $S$ 的SAM上面跑, 如果可以匹配就匹配, 不能匹配跳到后缀自动机的父亲节点上来移动左端点.
按照上面这样计算是对整串来说的. 因为还要考虑区间 $[l,r]$ 的事情, 我们用线段树合并维护出每个结点的right集合, 设当前匹配长度为 $len$, 那么只有当当前状态的right集合与 $[l+len-1,r]$ 有交集才说明与 $S[l:r]$ 匹配. 如果不满足这个条件, 不能按照SAM的普通套路直接跳prt, 而是应该让 $len$ 减少 $1$. 直接跳的话左端点会移动若干个位置, 可能会跳过最优长度. SAM普通套路直接跳prt是因为如果 $len$ 只减少 $1$ 而没有到达prt的长度的话依然没有改变当前状态不能匹配的事实.
然而直接这样计算铁定会有重复, 我们对 $T$ 的反串建SA求出所有前缀的最长公共后缀长度作为去重的参考信息. 按照SA求本质不同子串个数的套路, 重复的子串必然出现在后缀数组上相邻的两个后缀(注意是反串的后缀)上. 假设相邻的两个后缀 $i,j$ 的在原串的对应前缀的最大匹配长度分别是 $mlen_i,mlen_j$ 且它们的LCP是 $height$ 的话, 贡献就是 $mlen_j-\min(height,mlen_i)$.
实际上 $mlen_j$ 肯定不会小于 $\min(height,mlen_i)$, 因为这部分串是完全一样的. 所以直接减就行了.
以前用map的写法被UOJ 64位指针debuff给卡内存了qaq…然而指针线段树依然在被卡内存…UOJ变97分了QAQ
参考代码
之前听说今天minusT要更新Subterranean Rose? 完蛋在学校看不了qaq
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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
|
#include <bits/stdc++.h>
const int MAXN=1e6+10;
typedef long long intEx;
struct Node{
int l;
int r;
int sum;
Node* lch;
Node* rch;
Node(int,int);
void Insert(int);
int Query(int,int);
};
Node* N[MAXN];
int n;
int q;
int cnt=1;
int root=1;
int last=1;
int s[MAXN];
int SA[MAXN];
int len[MAXN];
int prt[MAXN];
int buc[MAXN];
int mlen[MAXN];
char buf[MAXN];
int rank[MAXN];
int height[MAXN];
int chd[MAXN][26];
int* x=new int[MAXN];
int* y=new int[MAXN];
void BuildSAM();
void Extend(char);
void BuildSA(char*,int);
Node* Merge(Node*,Node*);
int main(){
freopen("name.in","r",stdin);
freopen("name.out","w",stdout);
scanf("%s",buf+1);
n=strlen(buf+1);
for(int i=1;i<=n;i++)
Extend(buf[i]);
BuildSAM();
scanf("%d",&q);
while(q--){
int l,r;
scanf("%s",buf+1);
scanf("%d%d",&l,&r);
int m=strlen(buf+1);
int cur=root,curlen=0;
for(int i=1;i<=m;i++){
int x=buf[i]-'a';
while(cur!=root&&!chd[cur][x]){
cur=prt[cur];
curlen=len[cur];
}
if(chd[cur][x]){
++curlen;
cur=chd[cur][x];
while(cur!=root&&!N[cur]->Query(l+curlen-1,r)){
--curlen;
if(curlen<=len[prt[cur]])
cur=prt[cur];
}
}
mlen[i]=curlen;
}
std::reverse(buf+1,buf+m+1);
BuildSA(buf,m);
intEx ans=0;
int last=0;
for(int i=1;i<=m;i++){
ans+=(m-SA[i]+1)-height[i];
last=std::min(height[i],last);
ans-=mlen[m-SA[i]+1]-last;
last=mlen[m-SA[i]+1];
}
printf("%lld\n",ans);
}
return 0;
}
void BuildSAM(){
memset(buc,0,sizeof(int)*(n+1));
for(int i=1;i<=cnt;i++)
++buc[len[i]];
for(int i=1;i<=n;i++)
buc[i]+=buc[i-1];
for(int i=cnt;i>=1;i--)
s[buc[len[i]]--]=i;
for(int i=cnt;i>=1;i--)
N[prt[s[i]]]=Merge(N[prt[s[i]]],N[s[i]]);
}
void Extend(char ch){
int p=last;
int x=ch-'a';
int np=++cnt;
last=np;
len[np]=len[p]+1;
N[np]=new Node(1,n);
N[np]->Insert(len[np]);
while(p&&!chd[p][x])
chd[p][x]=np,p=prt[p];
if(!p)
prt[np]=root;
else{
int q=chd[p][x];
if(len[q]==len[p]+1)
prt[np]=q;
else{
int nq=++cnt;
memcpy(chd[nq],chd[q],sizeof(chd[q]));
N[nq]=new Node(1,n);
len[nq]=len[p]+1;
prt[nq]=prt[q];
prt[q]=nq;
prt[np]=nq;
while(p&&chd[p][x]==q)
chd[p][x]=nq,p=prt[p];
}
}
}
void Node::Insert(int x){
++this->sum;
if(this->l!=this->r){
int mid=(this->l+this->r)>>1;
if(x<=mid){
if(this->lch==NULL)
this->lch=new Node(this->l,mid);
this->lch->Insert(x);
}
else{
if(this->rch==NULL)
this->rch=new Node(mid+1,this->r);
this->rch->Insert(x);
}
}
}
int Node::Query(int l,int r){
if(l<=this->l&&this->r<=r)
return this->sum;
else{
int ans=0;
int mid=(this->l+this->r)>>1;
if(l<=mid&&this->lch)
ans+=this->lch->Query(l,r);
if(mid+1<=r&&this->rch)
ans+=this->rch->Query(l,r);
return ans;
}
}
Node* Merge(Node* a,Node* b){
if(a==NULL)
return b;
if(b==NULL)
return a;
Node* N=new Node(a->l,b->r);
N->sum=a->sum+b->sum;
N->lch=Merge(a->lch,b->lch);
N->rch=Merge(a->rch,b->rch);
return N;
}
void BuildSA(char* s,int n){
int m=127;
memset(buc+1,0,sizeof(int)*m);
for(int i=1;i<=n;i++)
++buc[x[i]=s[i]];
for(int i=1;i<=m;i++)
buc[i]+=buc[i-1];
for(int i=n;i>=1;i--)
SA[buc[x[i]]--]=i;
for(int k=1;k<n;k<<=1){
int p=0;
for(int i=n-k+1;i<=n;i++)
y[++p]=i;
for(int i=1;i<=n;i++)
if(SA[i]>k)
y[++p]=SA[i]-k;
memset(buc+1,0,sizeof(int)*m);
for(int i=1;i<=n;i++)
++buc[x[i]];
for(int i=1;i<=m;i++)
buc[i]+=buc[i-1];
for(int i=n;i>=1;i--)
SA[buc[x[y[i]]]--]=y[i];
std::swap(x,y);
x[SA[1]]=1;
p=1;
for(int i=2;i<=n;i++)
x[SA[i]]=(y[SA[i]]==y[SA[i-1]]&&y[SA[i]+k]==y[SA[i-1]+k])?p:++p;
if(p>=n)
break;
m=p;
}
for(int i=1;i<=n;i++)
rank[SA[i]]=i;
int k=0;
for(int i=1;i<=n;i++){
if(rank[i]==1)
continue;
if(k)
--k;
int j=SA[rank[i]-1];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])
++k;
height[rank[i]]=k;
}
}
Node::Node(int l,int r):l(l),r(r),sum(0),lch(NULL),rch(NULL){}
|
