Reincarnation

正因为梦易碎，才格外美好。

号家军集训 字符串选做

发表于 更新于 分类于
本文字数： 21k 阅读时长 ≈ 20 分钟

讲师：冯施源

动物园

题目简介

题目名称：动物园
题目来源： 具体不详

评测链接：https://www.luogu.com.cn/problem/P2375

形式化题意：给定一个字符串 ，设 表示 的前缀 长度不超过 的 个数，求 。对 取模。多测。

数据范围：

考虑 的性质，一个字符串的 的 也是这个字符串的 。

我们设 表示失配指针，那么就有 ，这就很好作答了。但这时如果直接求 是错误的，甚至比答案会大很多。很显然，我们还没有对 的长度进行限制。

那这意味着我们要把长度超限的 一一剔除，那很简单，直接跳 指针就行了，用的还是上面那个性质。至于时间复杂度分析，因为指针至多自加 次，所以还是 的。

AC Code
 
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
// ----- Eternally question-----
// Problem: P2375 [NOI2014] 动物园
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2375
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-24 20:29:35
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e6+10;
const int Mod=1e9+7;
int Test,N,Kmp[MAXN],Num[MAXN];
char Str[MAXN];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		scanf("%s",Str+1);
		N=std::strlen(Str+1);
		std::memset(Kmp,0,sizeof(Kmp));
		std::memset(Num,0,sizeof(Num));
		Num[1]=1;
		for(int i=2,j=0;i<=N;++i)
		{
			while(j&&Str[i]!=Str[j+1]) j=Kmp[j];
			if(Str[i]==Str[j+1]) ++j;
			Kmp[i]=j;Num[i]=Num[j]+1;
		}
		int ans=1;
		for(int i=2,j=0;i<=N;++i)
		{
			while(j&&Str[i]!=Str[j+1]) j=Kmp[j];
			if(Str[i]==Str[j+1]) ++j;
			while((j<<1)>i) j=Kmp[j];
			ans=ans*(ll)(Num[j]+1)%Mod;
		}
		write(ans,'\n');
	}
	return 0;
}
/*

*/

字符串的匹配

题目简介

题目名称：字符串的匹配
题目来源：

评测链接：https://darkbzoj.cc/problem/1461

形式化题意：给定一个长度为 的字符串 ，一个长度为 的字符串 ，求出所有的位置 使得 与 离散化后相同。

数据范围：

考虑对于普通的 多出了一个离散化，这意味着我们每一次比较字符的时候需要求出 在某一个区间的排名，所以在 上套一个主席树维护即可。

如果追求快捷的话，发现这个区间一定是一个单调的，也就是一个滑动窗口，所以可以直接使用树状数组维护即可。

题面挂了，没写。

SZA-Template

题目简介

题目名称：

题目来源： 具体不详

评测链接：https://www.luogu.com.cn/problem/P3426

形式化题意：给定一个字符串 ，现在要求用一个子串来印刷这个字符串，子串间可以重复，即你可以使用 来印刷 ，求能够成功印刷这个字符串的长度最小的子串。

数据范围：

考虑答案的上界就是 ，但这并不重要。我们考虑重复部分的性质。容易发现这就是那个子串的一个 。

我们设 表示子串 需要被印刷的最小印刷串长度。首先，印刷串一定是 的前缀，这个显然，而印刷串的后缀也一定是 的后缀，这个同样显然，而这个印刷串同样得在 的时候适可而止，意味着印刷串 也一定是 的后缀。那么， 就是 的一个真 ，于是，我们可以考虑从 入手这个题。

考虑 的贡献形式，根据 的性质，答案贡献一定只有 ，然后我们一个一个暴力判断的话，会被卡成 ，秉承字符串的线性构造，我们尝试优化这个做法。

我们考虑构造这个 来得到答案，如果当前 ，那么 ，因为这个子串并不存在 ，所有 ，也就是只能通过印刷这个串本身才能得到这个串。

然后考虑 的另外一种递推关系，肯定要从 入手，首先，如果对于 存在 ，这意味着我们选择的这个印刷串有另外一个更短的印刷串能够印刷这个印刷串，所以这个印刷串一定不是答案，因为一定存在更优解。

然后对于每一个 ，我们需要找到这个 每次在 中能够被匹配的位置，很明显，如果某两个匹配位置的距离 的话，这意味着中间有一个部分没有被覆盖到，则 同样无法成为答案。

那么我们已经把 的两种取值都找出来了，显然 一定会优于 ，所以我们找出什么情况下 才能被 转移。

考虑上面关于 距离的限制，所以，当 时，存在一个限制，那就是此时存在一个 使得 且 。

必定是 的一个前缀，而此时 是可以通过 来印刷的，而对于 这意味着 和 之间的差距 之间，相差这个子串的长度 ，这意味着什么？ 能够在 的基础上再印刷一次 来解决，也就做到了不留空隙的条件。

至于实现，我们对已经得到的备选答案开一个哈希就可以了。

AC Code
 
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
// ----- Eternally question-----
// Problem: P3426 [POI2005] SZA-Template
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3426
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-25 08:38:39
// ----- Endless solution-------

#include<bits/stdc++.Hash>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e6+10;
int Len,Kmp[MAXN];
char Str[MAXN];
int f[MAXN],Hash[MAXN];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	scanf("%s",Str+1);
	Len=std::strlen(Str+1);
	for(int i=2,j=0;i<=Len;++i)
	{
		while(j&&Str[i]!=Str[j+1]) j=Kmp[j];
		if(Str[i]==Str[j+1]) ++j;
		Kmp[i]=j;
	}
	f[1]=Hash[1]=1;
	for(int i=2;i<=Len;++i)
	{
		f[i]=i;
		if(Hash[f[Kmp[i]]]>=i-Kmp[i]) f[i]=f[Kmp[i]];
		Hash[f[i]]=i;
	}
	write(f[Len]);
	return 0;
}
/*

*/

回忆树

题目简介

题目名称：回忆树
题目来源：

评测链接：不详

形式化题意：有一棵边上有一个字符的树，给出 次询问，每次询问路径 中 出现的次数。

数据范围：

考虑将询问划分成三种：

  • 从 向祖先走的；
  • 从 向子树走到；
  • 跨过 的。

考虑前两种，我们对所有询问串建正反 自动机，然后遍历一遍 就能够统计所有答案，对于第三种，我们直接枚举 ，然后左右各拉出长度为 的链暴力匹配 即可。

好像是要用 和树上差分来维护，时间复杂度 ，具体细节等我写了再说。

阿狸的打字机

题目简介

题目名称：阿狸的打字机
题目来源： 具体不详

评测链接：https://www.luogu.com.cn/problem/P2414

形式化题意：给定一个操作串 以及一个初始为空的字符串集合 ，其中包含 个小写字母以及 B,P，其中 B 表示退格，P 表示将当前打印出的字符串加入到 中，但并不会清空当前打印序列。

一共 次操作，每次询问 中第 个字符串在第 个字符串中出现的次数。

数据范围：

这是一个类似于多模式串的匹配，所以首先考虑建出 自动机，这样的话，我们至少保证了每一次询问的查询是线性的，做到了 的复杂度，然后考虑优化。

容易发现，我们每一次询问就会把字符串 拿到 自动机上遍历一遍，那很显然的，我们可以把询问离线下来，然后对于所有 统一处理，这是好做的，但不一定会对时间复杂度产生什么影响，所以考虑进一步优化。

然后我们考虑对每一个询问点在 树上打标记，直接对 树进行 ，然后依据点进行询问处理，至于统计 的出现次数，我们可以直接维护 的 子树标记和，这个可以用 直接维护，所以到头来我们只需要遍历一遍 树即可。

时间复杂度 。

AC Code
 
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
// ----- Eternally question-----
// Problem: P2414 [NOI2011] 阿狸的打字机
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2414
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-05-22 11:28:56
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10;
char Str[MAXN];
int N,Q,Idx,Nd[MAXN],ans[MAXN];
int Tre[MAXN],Dfn[MAXN],Low[MAXN],Tim;
int Ql[MAXN],Qr[MAXN];
inline int lowbit(int x){ return x&(-x); }
inline void add(int x,int v){ for(;x<=Tim;x+=lowbit(x)) Tre[x]+=v; }
inline int query(int x)
{
	int res=0;
	for(;x;x-=lowbit(x)) res+=Tre[x];
	return res;
}
struct ACAM
{
	int to[26],vis[26];
	int fail,fa,lt;
}Tr[MAXN];
struct Question{ int x,y,id,ans; }Qry[MAXN];
bool operator<(Question a,Question b){ return a.y<b.y; }
inline void build()
{
	std::queue<int>Q;
	for(int i=0;i<26;++i) if(Tr[0].to[i]) Q.push(Tr[0].to[i]);
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		for(int i=0,v;i<26;++i)
		{
			if(!(v=Tr[u].to[i])) Tr[u].to[i]=Tr[Tr[u].fail].to[i];
			else Tr[v].fail=Tr[Tr[u].fail].to[i],Q.push(v);
		}
	}
}
struct G
{
	int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	// Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
void Dfs(int x)
{
	Dfn[x]=++Tim;
	for(int e=Head[x];e;e=Edge[e].next) Dfs(Edge[e].to);
	Low[x]=Tim;
}
void dfsTree(int x)
{
	add(Dfn[x],1);
	if(Tr[x].lt) for(int i=Ql[Tr[x].lt];i<=Qr[Tr[x].lt];++i)
		Qry[i].ans=query(Low[Nd[Qry[i].x]])-query(Dfn[Nd[Qry[i].x]]-1);
	for(int i=0;i<26;++i) if(Tr[x].vis[i]) dfsTree(Tr[x].vis[i]);
	add(Dfn[x],-1);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	scanf("%s",Str+1);
	for(int i=1,l=std::strlen(Str+1),u=0;i<=l;++i)
	{
		if(Str[i]>='a'&&Str[i]<='z')
		{
			if(!Tr[u].to[Str[i]-'a']) Tr[u].to[Str[i]-'a']=++Idx,Tr[Idx].fa=u;
			u=Tr[u].to[Str[i]-'a'];
		}
		if(Str[i]=='B') u=Tr[u].fa;
		if(Str[i]=='P') Nd[++N]=u,Tr[u].lt=N;
	}
	for(int i=0;i<=Idx;++i) for(int c=0;c<26;++c) Tr[i].vis[c]=Tr[i].to[c];
	read(Q);
	build();
	for(int i=1;i<=Idx;++i) addEdge(Tr[i].fail,i);
	Dfs(0);
	for(int i=1;i<=Q;++i)
	{
		read(Qry[i].x,Qry[i].y);
		Qry[i].id=i;
	}
	std::sort(Qry+1,Qry+Q+1);
	for(int i=1,pos=1;i<=Q;i=pos)
	{
		Ql[Qry[i].y]=i;
		while(Qry[pos].y==Qry[i].y) ++pos;
		Qr[Qry[i].y]=pos-1;
	}
	dfsTree(0);
	for(int i=1;i<=Q;++i) ans[Qry[i].id]=Qry[i].ans;
	for(int i=1;i<=Q;++i) write(ans[i],'\n');
	return 0;
}
/*

*/

A task for substrings

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/1801/G

形式化题意：给定一个模式串 以及 个匹配串 ，共 次询问，每次询问在 中每个串的出现个数和。

数据范围：

首先考虑对 建 自动机，然后把 扔上去跑，可以得到 表示 的答案。但很可惜，这个询问的贡献并不满足差分性质，所以无法直接通过 得到答案。

但是我们可以借助这个思想，因为得到 后，我们多统计了的部分满足一个条件，就是这个字符串的末尾在 中，而其开头在 中，也就是跨过了 部分的字符串。

所以相当于我们现在只需要统计跨过了 部分出现的字符串的总数。

我们把这个问题拆分，等价于在 中选择一个后缀，并在 中选择一个前缀，把两部分拼凑起来得到一个 的个数。

在 自动机中有一个非常优美的性质，对于一个前缀对应的结点 ，那么 在 树上所有的祖先所代表的字符串一定是这个前缀的后缀。这样我们就能在 时间内解决选择前缀的问题，可以直接倍增统计。

与之对应地，我们对反串建 自动机，找到这个后缀所代表的结点 ，则 在 树上所有的祖先所代表的字符串一定是这个后缀的前缀，同样用倍增统计就可以了。

然后我们把询问离线，对于每一个子树用 维护子树和，进入时统计，退出时撤销即可。时间复杂度 。

然后这个题有一个非常厉害的空间线性且在线的做法。

我们记录 表示以 为后缀的最长 的编号。

按照容斥的方法，找到最大的 使得 ，那么以 为结尾的 数量就等于 。而以 为右端点的 数量也就等于 的长度为 的后缀的合法子串数量。

那么记 表示 的长度为 的后缀有多少个同样合法的 ，直接构造正反串 自动机是好做的。

然后对于 可以直接选择线段树二分求即可。

时间复杂度 ，空间线性，可在线。

AC Code
 
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
// ----- Eternally question-----
// Problem: A task for substrings
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1801G
// Memory Limit: 1000 MB
// Time Limit: 4000 ms
// Written by: Eternity
// Time: 2023-07-25 10:42:41
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<int,int>;
#define fir first
#define sec second
const int MAXN=5e5+10,MAXT=1e6+10,MAXS=5e6+10,MAXC=27,MAXM=20;
int N,Q,Cnt;
int Ps[2][MAXT],Sx[MAXT],Sy[MAXT],Pos[MAXS],Rpos[MAXS];
ll ans[MAXS],Pre[MAXS];
std::vector<int>vec[MAXT];
std::vector<Pir>Qry[MAXT];
char Str[MAXS],T[MAXS];
struct BIT
{
	int Tre[MAXT],Siz;
	inline int lowbit(int x){ return x&(-x); }
	inline void build(int n){ Siz=n;for(int i=0;i<=n;++i) Tre[i]=0; }
	inline void add(int x,int v){ for(;x<=Siz;x+=lowbit(x)) Tre[x]+=v; }
	inline int query(int x)
	{
		int res=0;
		for(;x;x-=lowbit(x)) res+=Tre[x];
		return res;
	}
	inline int get(int l,int r){ return query(r)-query(l-1); }
}Tre;
struct ACAM
{
	int Tr[MAXT][MAXC],Fail[MAXT],L[MAXT],R[MAXT],Len[MAXT],Mul[MAXT][MAXM],Val[MAXT];
	int Idx=1,Dfns=0;
	std::vector<int>Edges[MAXT];
	std::queue<int>Q;
	inline void insert(char *s,int type)
	{
		int u=1;
		for(int i=0;s[i];++i)
		{
			int c=s[i]-'a';
			if(!Tr[u][c]) Tr[u][c]=++Idx,Len[Idx]=Len[u]+1;
			u=Tr[u][c],Ps[type][i+1]=u;
		}
	}
	void dfsTree(int x,int last)
	{
		L[x]=++Dfns,Mul[x][0]=last;
		for(int s=1;s<=19;++s) Mul[x][s]=Mul[Mul[x][s-1]][s-1];
		for(int v:Edges[x]) dfsTree(v,x);
		R[x]=Dfns;
	}
	inline void build()
	{
		for(int c=0;c<=25;++c)
			if(Tr[1][c]) Fail[Tr[1][c]]=1,Q.push(Tr[1][c]);
			else Tr[1][c]=1;
		while(!Q.empty())
		{
			int x=Q.front();Q.pop();
			Val[x]+=Val[Fail[x]];
			for(int c=0;c<=25;++c)
			{
				if(Tr[x][c]) Fail[Tr[x][c]]=Tr[Fail[x]][c],Q.push(Tr[x][c]);
				else Tr[x][c]=Tr[Fail[x]][c];
			}
		}
		for(int i=2;i<=Idx;++i) Edges[Fail[i]].push_back(i);
		dfsTree(1,0);
	}
	inline int get(int p,int k)
	{
		if(Len[p]<=k) return p;
		for(int s=19;~s;--s) if(Len[Mul[p][s]]>k) p=Mul[p][s];
		return Mul[p][0];
	}
}Frt,Bhd;
void solve(int x)
{
	for(int o:vec[x]) Tre.add(Bhd.L[o],1),Tre.add(Bhd.R[o]+1,-1);
	for(auto v:Qry[x]) ans[v.sec]-=Tre.query(Bhd.L[v.fir]);
	for(int v:Frt.Edges[x]) solve(v);
	for(int o:vec[x]) Tre.add(Bhd.L[o],-1),Tre.add(Bhd.R[o]+1,1);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q),scanf("%s",T);Tre.build(MAXT-1);
	for(int i=1;i<=N;++i)
	{
		scanf("%s",Str);
		int len=std::strlen(Str);
		Frt.insert(Str,0);
		std::reverse(Str,Str+len);
		Bhd.insert(Str,1);
		for(int l=1;l<len;++l) Sx[++Cnt]=Ps[0][l],Sy[Cnt]=Ps[1][len-l];
		++Frt.Val[Ps[0][len]];
	}
	Frt.build(),Bhd.build();
	for(int i=1;i<=Cnt;++i) vec[Sx[i]].push_back(Sy[i]);
	Pos[0]=1;
	int Len=std::strlen(T);
	for(int i=0,pos=1;i<Len;++i) pos=Frt.Tr[pos][T[i]-'a'],Pos[i+1]=pos,Pre[i+1]=Pre[i]+Frt.Val[pos];
	for(int i=Len-1,pos=1;~i;--i) pos=Bhd.Tr[pos][T[i]-'a'],Rpos[i+1]=pos;
	for(int i=1,ql,qr;i<=Q;++i)
	{
		read(ql,qr);
		ans[i]=Pre[qr]-Pre[ql-1];
		Qry[Pos[ql-1]].push_back({Bhd.get(Rpos[ql],qr-ql+1),i});
	}
	solve(1);
	for(int i=1;i<=Q;++i) write(ans[i],' ');
	return 0;
}
/*

*/

Substrings in a String

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/914/F

形式化题意：给定一个字符串 ，执行 次操作：

  • 执行 ，其中 为给定字符。
  • 求字符串 在子串 中的出现次数。

数据范围：

这道题有颇多的神秘做法，大概是官方题解既抽象又难写，所以大家就集思广义了吧。

Sol I

对 进行分块，然后对每一块分别建 （或之类的字符串科技），每次修改操作直接暴力重构所属块的数据结构。

对于询问，如果 ，那么直接暴力查询，这样的询问串个数不超过 ，时间复杂度在根号级别。如果 ，则我们可以用一种方法直接统计块内答案，暴力查询也是可以的。然后考虑跨块的答案，容易发现答案长度贡献不超过 ，所以直接把这个块长度为 的后缀和下一个块长度为 的前缀拉出来建 跑就可以了。

这个做法时间复杂度是大常数的 ，好像还过不了。

Sol II

暴力 查询的时间复杂度是 的，但很显然，我们依然可以向上面对询问分块，当 的时候暴力 匹配，否则直接使用字符串哈希来统计。这个可以分块做，也可以尝试一些 的数据结构（树状数组之类的），修改操作只需要修改长度在 之内的哈希值就可以了，这样的时间复杂度是 的，然后再开一个哈希存字符串哈希的值的个数就可以了。

时间复杂度是 ，平衡一下就可以了。但这个方法有点卡空间，注意把空哈希扔了减内存就行。

Sol III

经典 std::bitset 爆踩标算。

我们对字符集开一个 std::bitset，记录每一个字母在哪些位置出现过，然后在 bitset 上暴力匹配 ，并对其取交，然后直接统计一下就出来了。

时间复杂度 ，告诉你什么叫暴力踩标算。

AC Code
 
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
// ----- Eternally question-----
// Problem: F. Substrings in a String
// Contest: Codeforces - Codecraft-18 and Codeforces Round 458 (Div. 1 + Div. 2, combined)
// URL: https://codeforces.com/problemset/problem/914/F
// Memory Limit: 256 MB
// Time Limit: 6000 ms
// Written by: Eternity
// Time: 2023-07-25 16:09:30
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
int N,Q;
std::string S,T;
std::bitset<MAXN>a[27],ans;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	std::cin>>S,read(Q);
	for(int i=0;i<(int)S.size();++i) a[S[i]-'a'].flip(i);
	for(int opt,ql,qr;Q--;)
	{
		read(opt,ql),--ql;
		if(opt==1)
		{
			std::cin>>T;
			a[S[ql]-'a'].flip(ql),S[ql]=T[0];
			a[S[ql]-'a'].flip(ql);
		}
		else
		{
			read(qr),std::cin>>T,--qr;
			int len=T.size(); 
			if(len>qr-ql+1){ puts("0");continue; }
			ans.set();
			for(int i=0;i<len;++i) ans&=a[T[i]-'a']>>i;
			std::cout<<(ans>>ql).count()-(ans>>(qr-len+2)).count()<<std::endl;
		}
	}
	return 0;
}
/*

*/
相关文章