bzoj 4556 字符串

Posted on | Views:

$SAM$ + 倍增 + 线段树合并.

  • 这里有两个小性质需要注意.
    • 答案是可二分的.这个应该比较显然.
    • 两个子串的最长公共后缀就是它们在 $SAM$ 上状态节点 $LCA$ 的 $maxlen$ .想象两个串都从前往后缩短,当两者缩到同一个串,即公共后缀时,节点也跳到了它们的 $LCA$ .长度即为 $maxlen$ .
  • 于是把整个串翻转,询问前缀相关问题就变成了询问后缀相关问题.询问时,可以二分答案 $x$ ,转化为判定问题.
  • 从 $d$ 对应的位置用倍增往上跳,找到 $maxlen\geq x$ 的 $dep$ 最小的祖先(其 $right$ 集合最大,为最优),判断它的 $right$ 集合中是否出现了 $[a+x-1,b]$ 中的某个位置.
  • 如果出现了,那么从这个位置往前的 $x$ 个字符就是要找的子串,否则就找不到.
  • 可以看出 $c$ 的作用就是限制了二分答案 $x$ 的范围,显然不能超过 $d-c+1$ 与 $b-a+1​$ .
  • 一个点的 $right$ 集合是它所有儿子节点 $right$ 集合的并集.所以可以用线段树合并来维护.
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int Siz=26,MAXN=2e5+10;
int lst=1,idx=1;
int n,m;
int siz[MAXN],pos[MAXN],leafright[MAXN];
int ch[MAXN][Siz],fa[MAXN];
int len[MAXN];
void Extend(int c,int id)
{
	int p=lst,np=++idx;
	lst=np;
	pos[id]=np;
	leafright[np]=id;
	siz[np]=1;
	len[np]=len[p]+1;
	while(p && ch[p][c]==0)
		ch[p][c]=np,p=fa[p];
	if(p==0)
		fa[np]=1;	
	else
	{
		int q=ch[p][c];
		if(len[q]==len[p]+1)
			fa[np]=q;
		else
		{
			int nq=++idx;
			len[nq]=len[p]+1;
			fa[nq]=fa[q];
			fa[q]=fa[np]=nq;
			memcpy(ch[nq],ch[q],sizeof ch[q]);
			while(p && ch[p][c]==q)
				ch[p][c]=nq,p=fa[p];
		}
	}
}
int ecnt=0,head[MAXN],to[MAXN],nx[MAXN];
inline void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
int tot=0;
struct node
{
	int sum,ls,rs;
}Tree[MAXN*30];
#define root Tree[o]
#define lson Tree[root.ls]
#define rson Tree[root.rs]
void update(int &o,int l,int r,int pos)
{
	o=++tot;
	++root.sum;
	if(l==r)
		return;
	int mid=(l+r)>>1;
	if(pos<=mid)
		update(root.ls,l,mid,pos);
	else
		update(root.rs,mid+1,r,pos);
}
void pushup(int o)
{
	root.sum=lson.sum+rson.sum;
}
int merge(int x,int y)
{
	if(!x || !y)
		return x+y;
	int o=++tot;
	root.ls=merge(Tree[x].ls,Tree[y].ls);
	root.rs=merge(Tree[x].rs,Tree[y].rs);
	pushup(o);
	return o;
}
int query(int o,int l,int r,int L,int R)
{
	if(L>r || l>R)
		return 0;
	if(L<=l && r<=R)
		return root.sum;
	int mid=(l+r)>>1;
	int res=0;
	if(L<=mid)
		res+=query(root.ls,l,mid,L,R);
	if(R>mid)
		res+=query(root.rs,mid+1,r,L,R);
	return res;
}
int f[MAXN][18];
int rt[MAXN];
void mergeright(int u)
{
	f[u][0]=fa[u];
	for(int i=1;i<=17;++i)
		f[u][i]=f[f[u][i-1]][i-1];
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		mergeright(v);
		rt[u]=merge(rt[u],rt[v]);
	}
}
bool check(int x,int L,int R,int u)
{
	if(!x)
		return true;
	if(L>R)
		return false;
	for(int i=17;i>=0;--i)
		if(len[f[u][i]]>=x)
			u=f[u][i];
	return query(rt[u],1,n,L,R)>0;
}
char buf[MAXN];
int main()
{
	n=read(),m=read();
	scanf("%s",buf+1);
	for(int i=1;i<(n+1-i);++i)
		swap(buf[i],buf[n+1-i]);
	for(int i=1;i<=n;++i)
		Extend(buf[i]-'a',i);
	for(int i=1;i<=idx;++i)
		addedge(fa[i],i);
	for(int i=1;i<=idx;++i)
		if(leafright[i])
			update(rt[i],1,n,leafright[i]);
	mergeright(1);
	while(m--)
	{
		int a=read(),b=read(),c=read(),d=read();
		swap(a,b),swap(c,d);
		a=n+1-a,b=n+1-b,c=n+1-c,d=n+1-d;
		int L=0,R=min(d-c+1,b-a+1);
		int res=0;
		while(L<=R)
		{
			int mid=(L+R)>>1;
			if(check(mid,a+mid-1,b,pos[d]))
				res=max(res,mid),L=mid+1;
			else
				R=mid-1;
		}
		printf("%d\n",res);
	}
	return 0;
}