Reincarnation

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

Border & Period

发表于 更新于 分类于 ，
本文字数： 9.8k 阅读时长 ≈ 9 分钟

“雨落云霄，睁眼，便是黎明。”

Border 与 Period

这是一个与字符串基础有关的东西，但我们现在要做的是深究其性质。

的定义我们在 算法和 自动机中都有提到过，而 的定义我们则在 算法中有过说明。

定义一个长度为 的字符串 的 ，指的是一个数 满足 ，我们将这个子串，满足既是 的前缀又是 的后缀的子串称为 的 。

同样的，我们定义 ，称一个数 使得 满足 ，则子串 是 的一个 ，其中 称为其 长度。一般将 称为字符串的周期。将最小周期记为 。

显然地，根据 和 的定义，如果 的子串 是 的 ，这意味着 是 的一个 。

弱周期引理与周期引理

首先给出弱周期定理（），内容如下：

若 是 的周期，且 ，那么 也是 的周期。

证明

我们这里假设 ，记 。

因为有 ，那么对于 ，则 和 必有一成立。

  • 若 成立，则有 ；
  • 若 成立，则有 。

所以，无论如何， 都是 的周期。这个过程就是 的辗转相除过程，以此类推， 也是 的周期。

然后是周期引理（），内容如下：

如果 是 的周期，且 ，则 是 的周期。

证明

还是考虑 ，记 。

前面我们已经证得当 时 是 的周期。那么显然 是长度为 的一个前缀或后缀的循环节。

因为 ，所以 。所以 也同样是长度为 的一个前缀或后缀的循环节。而 ，所以这个前缀是由若干个完整的 组成的。

我们把 视作一个长度为 的前缀与一个长度为 的后缀的组合。而我们已经证明了 是 和 的前缀或后缀的循环节，所以 是 的循环节。

所以 是 的周期。

字符串匹配

若字符串 满足 ，那么 在 中所有出现的位置构成一个等差数列，公差为 。

证明

考虑此时 中存在 有至少三次匹配，其中第一次匹配和第二次匹配的距离为 ，设第二次匹配与后面某一次匹配的距离为 。

显然地，因为 ，所以 都是 的一个周期。那根据周期引理，因为 ，显然 也是 的周期。

那么 或 成立，则 。

如果 存在一些 的长度不小于 ，那么这些 的位置构成等差数列。

证明

考虑同样用辗转相减的方式来证明，我们可以首先指定一个长度未过半的 ，然后递归处理 ，得到 中的过半 ，然后证明这些新的 都是最长的 的过半 ，对于左半边处理前缀，右半边处理后缀即可。

记 最长的 为 ，其中 ，并记存在另外一个 为 ，一样有 。

那么显然 是 的周期，而 ，所以 也是 的周期。反之， 是一个周期。而 ，且 是最大周期，那只有 才合法。所以 。

所有 从小到大排序最多形成 个等差数列。

如果 是回文串，如果 是 的回文后缀，那么 一定是 的 。

Border 的四种求法

题目简介

题目名称： 的四种求法

题目来源： 具体不详

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

形式化题意：给定一个长度为 的字符串，共 次询问，每次询问 的最长 。

数据范围：

考虑 的本质，求 的 等价于选择最大的 满足 ，这个问题不能 二分，因为不具有单调性。

考虑前缀的 在 的 的形态，就是 表示的长度。那我们可以考虑用线段树合并处理 等价类，枚举 的祖先 ，找到 中满足在 中最大的。

上述方法是可以被卡到 的，但是因为数据过水能过。

考虑进一步转化，令结点 表示字符串前缀 ，那么我们需要从 中找到一个结点 表示 并满足 的最大的 。

我们考虑在 上树链剖分，我们对每一条重链分开考虑，记其中深度最大的点为 ，重链顶端为 ，则贡献可以为：

  • 从 的子树中取一个点；
  • 从重链中比 深度浅的点中选择。
  • 从重链中比 深度浅的点的轻子树中选择。

这样我们就保证了至少不漏，对于子树，我们考虑线段树合并，在 的时间复杂度内解决。对于重链，我们发现重链和轻子树大小之和不超过 ，这样可以解决。

我们维护一棵线段树，下标 存储 的值，那这样上面的问题我们可以线段树二分解决。

询问离线，找到每一段最深的点，统一处理询问。

时间复杂度 ，空间复杂度 。

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
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
// ----- Eternally question-----
// Problem: P4482 [BJWC2018] Border 的四种求法
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4482
// Memory Limit: 512 MB
// Time Limit: 5000 ms
// Written by: Eternity
// Time: 2023-07-28 09:37:05
// ----- 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=4e5+10;
const int INF=0x3f3f3f3f;
int N,Q,Rt[MAXN],Idx=0;
struct Segment
{
	struct Seg
	{ int lc,rc; }Tr[MAXN<<6];
	#define ls(p) Tr[p].lc
	#define rs(p) Tr[p].rc
	void modifyX(int &p,int l,int r,int x)
	{
		if(!p) p=++Idx;
		if(l==r) return ;
		int mid=(l+r)>>1;
		x<=mid?modifyX(ls(p),l,mid,x):modifyX(rs(p),mid+1,r,x);
	}
	int queryKth(int p,int l,int r,int k)
	{
		if(!p||k<=0) return 0;
		if(l==r) return l;
		int mid=(l+r)>>1,res=0;
		if(k>mid) res=queryKth(rs(p),mid+1,r,k);
		if(res) return res;
		return queryKth(ls(p),l,mid,k);
	}
	int merge(int p1,int p2,int l,int r)
	{
		if(!p1||!p2) return p1^p2;
		if(l==r) return p1;
		int p=++Idx,mid=(l+r)>>1;
		ls(p)=merge(ls(p1),ls(p2),l,mid),
		rs(p)=merge(rs(p1),rs(p2),mid+1,r);
		return p;
	}
	#undef ls
	#undef rs
}Tre;
struct SegmtTre
{
	int Tr[MAXN<<2];
	#define ls (p<<1)
	#define rs (p<<1|1)
	void build(int p,int l,int r)
	{
		Tr[p]=INF;
		if(l==r) return ;
		int mid=(l+r)>>1;
		build(ls,l,mid),build(rs,mid+1,r);
	}
	void modifyX(int p,int l,int r,int x,int v)
	{
		if(l==r) return Tr[p]=v,void();
		int mid=(l+r)>>1;
		x<=mid?modifyX(ls,l,mid,x,v):modifyX(rs,mid+1,r,x,v);
		Tr[p]=std::min(Tr[ls],Tr[rs]);
	}
	int queryMin(int p,int l,int r,int k,int lim)
	{
		if(Tr[p]>=lim) return 0;
		if(l==r) return Tr[p]<lim?l:0;
		int mid=(l+r)>>1,res=0;
		if(k>mid) res=queryMin(rs,mid+1,r,k,lim);
		if(res) return res;
		return queryMin(ls,l,mid,k,lim);
	}
	#undef ls
	#undef rs
}Tr;
struct SAM
{
	int nxt[MAXN][27],fail[MAXN],len[MAXN],ep[MAXN];
	int last,Tot;
	SAM(){ last=Tot=1; }
	void extend(int c,int dex)
	{
		int p=last,cur=++Tot;
		len[cur]=len[p]+1,last=cur,ep[cur]=dex;
		while(p&&!nxt[p][c]) nxt[p][c]=cur,p=fail[p];
		if(!p) return fail[cur]=1,void();
		int q=nxt[p][c];
		if(len[q]==len[p]+1) return fail[cur]=q,void();
		int cl=++Tot;
		std::memcpy(nxt[cl],nxt[q],sizeof(nxt[q]));
		len[cl]=len[p]+1,fail[cl]=fail[q];
		fail[cur]=fail[q]=cl;
		while(p&&nxt[p][c]==q) nxt[p][c]=cl,p=fail[p];
	}
	struct Query
	{ int l,r,id; };
	std::vector<Query>Qry[MAXN];
	int ans[MAXN];
	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;
	}
	int Siz[MAXN],Dep[MAXN],Son[MAXN],Fa[MAXN];
	void dfsTree(int x,int last)
	{
		Fa[x]=last,Siz[x]=1,Dep[x]=Dep[last]+1;
		if(ep[x]) Tre.modifyX(Rt[x],1,N,ep[x]);
		for(int e=Head[x],v;e;e=Edge[e].next)
		{
			if((v=Edge[e].to)==last) continue;
			dfsTree(v,x);
			Siz[x]+=Siz[v];
			if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
			Rt[x]=Tre.merge(Rt[x],Rt[v],1,N);
		}
	}
	int Dfn[MAXN],Top[MAXN],Cnt;
	void dfsChain(int x,int topf)
	{
		Top[x]=topf,Dfn[x]=++Cnt;
		if(Son[x]) dfsChain(Son[x],topf);
		for(int e=Head[x],v;e;e=Edge[e].next)
		{
			if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
			dfsChain(v,v);
		}
	}
	inline void build()
	{
		for(int i=2;i<=Tot;++i) addEdge(fail[i],i);
		dfsTree(1,0),dfsChain(1,1);
	}
	void push(int u,int k)
	{
		if(ep[u]) Tr.modifyX(1,1,N,ep[u],ep[u]-k);
		for(int e=Head[u];e;e=Edge[e].next) push(Edge[e].to,k);
	}
	void back(int u)
	{
		if(ep[u]) Tr.modifyX(1,1,N,ep[u],INF);
		for(int e=Head[u];e;e=Edge[e].next) back(Edge[e].to);
	}
	void solve(int s)
	{
		for(int u=s;u;u=Son[u])
		{
			if(ep[u]) Tr.modifyX(1,1,N,ep[u],ep[u]-len[u]);
			for(int e=Head[u];e;e=Edge[e].next) if(Edge[e].to!=Son[u]) push(Edge[e].to,len[u]);
			for(auto x:Qry[u])
			{
				int res=Tre.queryKth(Rt[u],1,N,std::min(x.r-1,x.l+len[u]-1));
				if(res>=x.l) checkMax(ans[x.id],res-x.l+1);
				res=Tr.queryMin(1,1,N,x.r-1,x.l);
				if(res>=x.l) checkMax(ans[x.id],res-x.l+1);
			}
		}
		for(int u=s;u;u=Son[u])
		{
			if(ep[u]) Tr.modifyX(1,1,N,ep[u],INF);
			for(int e=Head[u];e;e=Edge[e].next) if(Edge[e].to!=Son[u]) back(Edge[e].to);
		}
		for(int u=s;u;u=Son[u])
			for(int e=Head[u];e;e=Edge[e].next) if(Edge[e].to!=Son[u]) solve(Edge[e].to);
	}
}Sam;
int Ed[MAXN];
char Str[MAXN];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	scanf("%s",Str+1);
	N=std::strlen(Str+1);
	for(int i=1;i<=N;++i) Sam.extend(Str[i]-'a',i),Ed[i]=Sam.last;
	Sam.build();
	read(Q);
	for(int i=1,ql,qr;i<=Q;++i)
	{
		read(ql,qr);
		if(ql==qr){ Sam.ans[i]=0;continue; }
		int ps=Ed[qr];
		while(ps) Sam.Qry[ps].push_back({ql,qr,i}),ps=Sam.fail[Sam.Top[ps]];
	}
	Tr.build(1,1,N),Sam.solve(1);
	for(int i=1;i<=Q;++i) write(Sam.ans[i],'\n');
	return 0;
}
/*

*/
相关文章