[BZOJ 4556][Tjoi2016&Heoi2016]字符串

rvalue 收录于 cnblogs 题解

2019-02-14 约 868 字预计阅读 2 分钟

迁移提示

本文迁移自博客园, 原文链接

[BZOJ 4556] 字符串

题意

原题面

给定一个长度为 $n$ 的串 $s$, $m$ 次查询 $s[a:b]$ 的所有子串与 $s[c:d]$ 的LCP的最大值.

$1\le n,m\le1\times 10^5$

题解

据说后缀数组挺好做的?

管他呢反正垃圾rvalue只会用SAM做题(QAQ)

首先SAM比较好搞的是子串公共后缀 (right集合出发的长度一定的后缀) , 于是我们把原串 std::reverse 一下再搞.

翻转之后要做的就是查询 $s[a:b]$ 的所有子串与 $s[c:d]$ 的最长公共后缀的最大值.

容易小于最优解的公共后缀对应的子串是可以构造出来的, 于是答案是可以二分的. 我们二分这个答案为 mid. 则我们要做的就是查询 $s[d-mid+1:d]$ 是否是 $s[a:b]$ 的子串.

我们如果能够定位到 $s[d-mid+1:d]$ 在SAM上运行后的状态, 那么显然这个状态的right集合的位置都是 $s[d-mid+1:d]$ 在 $s$ 中的出现位置的右端点. 于是只要right集合中有 $[a+mid-1,b]$ 内的值则代表当前二分的答案合法.

定位某个子串在SAM上运行后的状态的一般做法是在prt树上倍增. 查询 $s[l:r]$ 的状态时, 从代表 $s[:r]$ 的状态(这个可以在构造时存储)出发向上跳, 找到第一个 $len(p)\ge r-l+1$ 的状态 $p$ 即可. (再向上跳必然会导致 $len(p)<r-l+1$, 于是当前的 $p$ 满足 $len(prt(p))<r-l+1\le len(p)$, 易知 $p$ 包含 $s[l:r]$).

求right集合可以用线段树合并解决. 动态开点线段树合并的复杂度是有保证的 ($O(\log n)$).

参考代码

  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


#include <bits/stdc++.h>

const int MAXN=2e5+10;

struct Node{
	int l;
	int r;
	int sum;
	Node* lch;
	Node* rch;
	Node(int,int,int=0);
	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 len[MAXN];
int end[MAXN];
char str[MAXN];
int scnt[MAXN];
int pprt[20][MAXN];
int* prt=pprt[0];
std::map<char,int> chd[MAXN];

void BucSort();
int Extend(char);
inline void Rev(int&);
Node* Merge(Node*,Node*);
bool Check(int,int,int,int,int);

int main(){
	scanf("%d%d",&n,&q);
	scanf("%s",str+1);
	std::reverse(str+1,str+1+n);
	for(int i=1;i<=n;i++){
		end[i]=Extend(str[i]);
		N[end[i]]=new Node(1,n);
		N[end[i]]->Insert(i);
	}
	BucSort();
	for(int i=cnt;i>=1;i--)
		N[prt[s[i]]]=Merge(N[prt[s[i]]],N[s[i]]);
	int lg;
	for(lg=1;(1<<lg)<cnt;lg++)
		for(int i=cnt;i>=1;i--)
			pprt[lg][i]=pprt[lg-1][pprt[lg-1][i]];
	while(q--){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		Rev(a),Rev(b),Rev(c),Rev(d);
		std::swap(a,b),std::swap(c,d);
		int l=0,r=std::min(d-c+1,b-a+1)+1;
		while(r-l>1){
			int mid=(l+r)>>1;
			int p=end[d];
			for(int i=lg;i>=0;i--){
				if(len[pprt[i][p]]&gt;=mid)
					p=pprt[i][p];
			}
			if(N[p]->Query(a+mid-1,b))
				l=mid;
			else
				r=mid;
		}
		printf("%d\n",l);
	}
	return 0;
}

void BucSort(){
	memset(scnt,0,sizeof(scnt));
	for(int i=1;i<=cnt;i++)
		++scnt[len[i]];
	for(int i=1;i<=cnt;i++)
		scnt[i]+=scnt[i-1];
	for(int i=cnt;i>=1;i--)
		s[scnt[len[i]]--]=i;
}

int Extend(char x){
	int p=last;
	int np=++cnt;
	last=np;
	len[np]=len[p]+1;
	while(p&&!chd[p].count(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;
			len[nq]=len[p]+1;
			chd[nq]=chd[q];
			prt[nq]=prt[q];
			prt[q]=nq;
			prt[np]=nq;
			while(p&&chd[p][x]==q)
				chd[p][x]=nq,p=prt[p];
		}
	}
	return np;
}

void Node::Insert(int x){
	++this->sum;
	if(l!=r){
		int mid=(l+r)>>1;
		if(x<=mid){
			if(this->lch==NULL)
				this->lch=new Node(l,mid);
			this->lch->Insert(x);
		}
		else{
			if(this->rch==NULL)
				this->rch=new Node(mid+1,r);
			this->rch->Insert(x);
		}
	}
}

Node* Merge(Node* a,Node* b){
	if(a==NULL)
		return b;
	if(b==NULL)
		return a;
	Node* tmp=new Node(a->l,a->r,a->sum+b->sum);
	tmp->lch=Merge(a->lch,b->lch);
	tmp->rch=Merge(a->rch,b->rch);
	return tmp;
}

Node::Node(int l,int r,int sum):l(l),r(r),sum(sum),lch(NULL),rch(NULL){}

inline void Rev(int& x){
	x=n-x+1;
}

int Node::Query(int l,int r){
	if(l<=this->l&&this->r<=r)
		return this->sum;
	else{
		int ans=0;
		if(this->lch&&l<=this->lch->r)
			ans+=this->lch->Query(l,r);
		if(this->rch&&this->rch->l<=r)
			ans+=this->rch->Query(l,r);
		return ans;
	}
}

目录

[BZOJ 4556][Tjoi2016&Heoi2016]字符串

[BZOJ 4556] 字符串

题意

题解

参考代码