字符串[FJWC2020Day3]

发表于 分类于 ，

题意

你喜欢字符串。有人送了你一个仅含小写字母的字符串。

由于你是一名优秀的 𝑂𝐼er，所以你决定对这个字符串展开研究。

定义两个字符串是相似的，当且仅当存在至多一个 $i$ ，使得这两个字符串中只有第 $i$ 个字母不同。

你取出了这个字符串中所有长度为 $m$ 的子串。你想知道，对于每个长度为 $m$ 的子串，有多少个其它长度为 $m$ 的子串与它相似。

$n\leq 10^5$

题解

也不知为啥别人的可以这么短。。。

显然，两个字符串 $i,j$ 是相似的当且仅当 $lcp(i,j)+lcs(i+m-1,j+m-1)\geq m-1$。

那么分别对正串和反串建出 SAM 的建出两棵树，记 $P1_i$ 和 $P2_i$ 表示第 $i$ 个长度为 $m$ 的字符串在两棵树中的所在的位置，那么上面的条件就是 $len_{lca1(P1_i,P1_j)}+len_{lca2(P2_i,P2_j)}\geq m-1$。

那么，我们可以对两棵树进行处理。

首先对第一棵树进行dsu on tree。枚举第一棵树的lca，那么上述条件就是 $len_{lca2(P2_i,P2_j)}\geq m-1-len_{lca}$

先递归处理轻儿子，然后将贡献删掉。然后递归重儿子，保留其贡献。

我们只需要考虑：

轻儿子节点之间的贡献

对于一个节点 $u$，将轻儿子从左到右排成一列，只考虑 $j<i$ 时 $j$ 对 $i$ 的贡献（否则反过来再处理一遍就可以了），那么枚举第 $i$ 个轻儿子的子树中的节点，考虑之前的所有节点，要使得在第二棵树上的 $len_{lca2}$ 大于等于 $k=m-1-len_{lca}$，那么用倍增找到这个节点在第二棵树上的祖先中最浅的节点 $w$，使得 $len_w\geq k$。

之后就在 $w$ 的子树中找有多少个节点满足这个节点在第一棵树中在 $j$ 的子树里。这个是一个单点加，区间查询，用树状数组维护即可。

重儿子对轻儿子的贡献

显然你不能再枚举一遍重儿子，那么再维护一个树状数组（表示的就是上面所说的贡献），意义跟第一种情况是几乎一样的，然后枚举轻儿子的所有节点，倍增，然后查询即可。

轻儿子对重儿子的贡献

显然你不能再枚举一遍重儿子，那么对于一个轻儿子子树中的节点 $v$ 而言，设它在一种情况中的 $w$ 是 $w_v$，那么所有满足在第一棵树重儿子的子树中且在第二棵树 $w_v$ 的子树中的节点的答案需要加 $1$。

这是一个矩形加，最后再单点查询的问题。

那么将矩形加离线，然后扫描线+树状数组解决即可。

综上，时间复杂度是 $O(n\log^2n)$ 的。

程序

也就接近300行而已。。。

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
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=2e5+5;
int n,m,cnt;
int c[N],d[N];
ll ans[N];
namespace BIT{
	inline void add(int *b,int x,int d)
	{
		for(;x<=cnt;x+=lowbit(x)) b[x]+=d;
	}
	inline void add(int *b,int l,int r,int d)
	{
		add(b,l,d); add(b,r+1,-d);
	}
	inline int ask(int *b,int x)
	{
		int s=0;
		for(;x;x-=lowbit(x)) s+=b[x];
		return s;
	}
	inline int ask(int *b,int l,int r)
	{
		return ask(b,r)-ask(b,l-1);
	}
}
namespace SAM{
	int ne[N][26],len[N],fa[N],siz,las;
	void init()
	{
		fo(i,0,siz) memset(ne[i],0,sizeof(ne[i])),len[i]=fa[i]=0;
		siz=las=1;
	}
	inline int extend(int c)
	{
		int cur=++siz,p=las;
		len[cur]=len[p]+1;
		for(;p&&!ne[p][c];p=fa[p]) ne[p][c]=cur;
		if(!p) fa[cur]=1;
		else
		{
			int q=ne[p][c];
			if(len[q]==len[p]+1) fa[cur]=q;
			else
			{
				int np=++siz;
				len[np]=len[p]+1;
				memcpy(ne[np],ne[q],sizeof(ne[q]));
				fa[np]=fa[q];
				for(;p&&ne[p][c]==q;p=fa[p]) ne[p][c]=np;
				fa[cur]=fa[q]=np;
			}
		}
		las=cur;
		return las;
	}
}
namespace T2{
	vector<int> adj[N];
	int dfl[N],dfr[N],tim,f[N][18],len[N],p[N],id[N];
	inline void addtree(int x,int y) {adj[x].pb(y);}
	void pre_dfs(int u)
	{
		dfl[u]=++tim;
		fo(i,1,17) f[u][i]=f[f[u][i-1]][i-1];
		for(auto v:adj[u]) f[v][0]=u,pre_dfs(v);
		dfr[u]=tim;
	}
	inline int jump(int x,int d)
	{
		fd(i,17,0) if(f[x][i]&&len[f[x][i]]>=d) x=f[x][i];
		return x;
	}

}
namespace T1{
	vector<int> adj[N];
	int dfl[N],dfr[N],tim,id[N],p[N],siz[N],son[N],len[N];
	inline void addtree(int x,int y) {adj[x].pb(y);}
	void pre_dfs(int u)
	{
		siz[u]=1; dfl[u]=++tim;
		for(auto v:adj[u])
		{
			pre_dfs(v);
			siz[u]+=siz[v];
			if(siz[son[u]]<siz[v]) son[u]=v;
		}
		dfr[u]=tim;
	}
	int _w[N];
	inline void add(int u,int dd)
	{
		if(id[u]) BIT::add(c,T2::dfl[T2::p[id[u]]],dd);
	}
	inline void ask(int u,int k)
	{
		if(!id[u]) return;
		int t=id[u],v=T2::p[t],w=T2::jump(v,k);
		_w[u]=w;
		ans[t]+=BIT::ask(c,T2::dfl[w],T2::dfr[w]);
	}
	void add_dfs(int u,int d)
	{
		add(u,d);
		for(auto v:adj[u]) add_dfs(v,d);
	}
	void ask_dfs(int u,int k)
	{
		ask(u,k);
		for(auto v:adj[u]) ask_dfs(v,k);
	}
	
	inline void calc_d(int u)
	{
		if(!id[u]) return;
		int t=id[u],w=_w[u];
		ans[t]+=BIT::ask(d,T2::dfl[w],T2::dfr[w]);
	}
	inline void add_d(int u,int dd)
	{
		if(id[u]) BIT::add(d,T2::dfl[T2::p[id[u]]],dd);
	}
	void add_d_dfs(int u,int d)
	{
		add_d(u,d);
		for(auto v:adj[u]) add_d_dfs(v,d);
	}
	void calc_d_dfs(int u)
	{
		calc_d(u);
		for(auto v:adj[u]) calc_d_dfs(v);
	}
	struct query{
		int l,r,d;
	};
	vector<query> q[N];
	int l,r;
	inline void ins(int u)
	{
		if(!id[u]) return;
		int w=_w[u];
		q[l].pb((query){T2::dfl[w],T2::dfr[w],1});
		q[r+1].pb((query){T2::dfl[w],T2::dfr[w],-1});
	}
	void ins_dfs(int u)
	{
		ins(u);
		for(auto v:adj[u]) ins_dfs(v);
	}
	void dfs(int u,bool flag)
	{
		int tot=adj[u].size(),v,k=m-1-len[u];
		ff(i,0,tot)
		{
			v=adj[u][i];
			if(v==son[u]) continue;
			dfs(v,0);
		}
		if(son[u]) dfs(son[u],1);
		ask(u,k);
		add(u,1);
		ff(i,0,tot)
		{
			v=adj[u][i];
			if(v==son[u]) continue;
			ask_dfs(v,k); add_dfs(v,1);
		}
		add(u,-1);
		ff(i,0,tot)
		{
			v=adj[u][i];
			if(v==son[u]) continue;
			add_dfs(v,-1);
		}
		fd(i,tot-1,0)
		{
			v=adj[u][i];
			if(v==son[u]) continue;
			ask_dfs(v,k); add_dfs(v,1);
		}
		ask(u,k);
		ff(i,0,tot)
		{
			v=adj[u][i];
			if(v==son[u]) continue;
			add_dfs(v,-1);
		}

		calc_d(u);
		ff(i,0,tot)
		{
			v=adj[u][i];
			if(v==son[u]) continue;
			calc_d_dfs(v);
		}
		if(flag)
		{
			add_d(u,1);
			ff(i,0,tot)
			{
				v=adj[u][i];
				if(v==son[u]) continue;
				add_d_dfs(v,1);
			}
		}
		else if(son[u]) add_d_dfs(son[u],-1);

		if(!son[u]) return;
		l=dfl[son[u]],r=dfr[son[u]];
		ins(u);
		ff(i,0,tot)
		{
			v=adj[u][i];
			if(v==son[u]) continue;
			ins_dfs(v);
		}
	}
	int g[N];
	inline void work()
	{
		dfs(1,0);
		fo(i,1,n-m+1) g[dfl[p[i]]]=i;
		int si=tim;
		memset(c,0,sizeof(c));
		fo(i,1,si)
		{
			for(auto x:q[i]) BIT::add(c,x.l,x.r,x.d);
			if(!g[i]) continue;
			ans[g[i]]+=BIT::ask(c,T2::dfl[T2::p[g[i]]]);
		}
	}
}
char s[N];
int main()
{
	n=read(); m=read();
	scanf("%s",s+1);
	SAM::init();
	int x;
	fo(i,1,n)
	{
		x=SAM::extend(s[i]-'a');
		if(i>=m) T1::p[i-m+1]=x,T1::id[x]=i-m+1;
	}
	fo(i,2,SAM::siz) T1::addtree(SAM::fa[i],i);
	fo(i,1,SAM::siz) T1::len[i]=SAM::len[i];
	SAM::init();
	fd(i,n,1)
	{
		x=SAM::extend(s[i]-'a');
		if(i+m-1<=n) T2::p[i]=x,T2::id[x]=i;
	}
	fo(i,2,SAM::siz) T2::addtree(SAM::fa[i],i);
	fo(i,1,SAM::siz) T2::len[i]=SAM::len[i];
	cnt=SAM::siz;
	T1::pre_dfs(1);
	T2::pre_dfs(1);
	T1::work();
	fo(i,1,n-m+1) printf("%lld ",ans[i]);
	return 0;
}