「雅礼集训 2017 Day1」字符串 题解

思路

先考虑如何快速判断一个模式串的子串在文本串内的出现次数，假设子串所在区间为 $[l_i,r_i]$，则等价于计算文本串有多少个后缀与子串的 $LCP$（最长公共前缀）长度 $\ge r_i-l_i+1$，那么可以想到建一个后缀数组，把文本串和模式串放进一个字符串，中间用特殊符号隔开（比如 #），就可以 $O(1)$ 查询两个后缀的 $LCP$。要查询所有满足条件的后缀，只需要在 $sa$ 数组上二分出满足条件的左右界，其中属于文本串的后缀数量就是答案。

那么就有了一个比较暴力的思路，对于所有模式串，暴力遍历每一个他的查询区间，用后缀数组查询每一个查询区间的答案即可，这样时间复杂度是 $O(qm \log n)$ 的。

但是我们注意到 $q\times k=\sum |w|\le 10^5$，考虑根号分治。

当 $q<k$ 时，可以用上面的 $O(qm \log n)$ 的算法。

当 $q \ge k$ 时，原本的方法会超时。但是我们注意到由于 $k$ 不会太大，所以查询区间的种类数也不会太多，不会超过 $k^2$，那么对于每一个模式串预处理出所有查询区间 $[l_i,r_i]$ 的答案，再看模式串查询的查询区间的区间与查询 $[l_i,r_i]$ 的区间编号的交集大小（二分即可）乘上预处理出的答案即为查询区间 $[l_i,r_i]$ 的答案和，最后全部累加起来即可，时间复杂度 $O(qk^2 \log n)$。

这样这题就做完了，视 $n,m,qk$ 同阶，时间复杂度为 $O(n\sqrt n \log n)$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxl=2e5+10;
int N,M,P,sa[mxl],rk[mxl],oldrk[mxl],cnt[mxl],id[mxl],st[mxl][25],lg2[mxl];//SA用 
ll tot[mxl];//SA属于文本串的后缀的前缀和 
int n,m,q,k,l[100010],r[100010],sti[100010],x[100010],y[100010];
vector<int> cntt[350][350];//记录每个种类查询区间的编号 
 int get(int l,int r){//SA求LCP 
	if(l==r)return 1919810;
	if(l>r)swap(l,r);
	r--;
	int d=lg2[r-l+1];
	return (st[l][d]<st[r-(1<<d)+1][d])?st[l][d]:st[r-(1<<d)+1][d];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>q>>k;
	int fl=(q>=k);//根号分治 
	for(int i=2;i<=n+q*k+1;i++)lg2[i]=lg2[i>>1]+1;//预处理log2(i) 
	string s;
	cin>>s;
	s+='#';//文本串与模式串之间的间隔符号 
	for(int i=1;i<=m;i++){
		cin>>l[i]>>r[i];
		if(fl)cntt[l[i]][r[i]-l[i]+1].push_back(i);//记录区间的编号 
	}
	if(fl){
		for(int i=0;i<k;i++){
			for(int j=1;j<=k;j++)if(cntt[i][j].size()>0){
				sort(cntt[i][j].begin(),cntt[i][j].end());//给每个种类区间的编号排序（后面要二分） 
			}
		}
	}
	for(int i=1;i<=q;i++){
		string t;
		cin>>t;
		sti[i]=s.size()+1;//记录每个模式串在总串的位置 
		s+=t;
		cin>>x[i]>>y[i];
		x[i]++;y[i]++;
	}
	//求SA 
	N=s.size();
	s=" "+s;
	M=255;
	for(int i=1;i<=N;i++)cnt[rk[i]=s[i]]++;
	for(int i=1;i<=M;i++)cnt[i]+=cnt[i-1];
	for(int i=N;i;i--)sa[cnt[rk[i]]--]=i;
	for(int w=1;P<N;w<<=1,M=P){
		int cur=0;
		for(int i=N-w+1;i<=N;i++)id[++cur]=i;
		for(int i=1;i<=N;i++)if(sa[i]>w)id[++cur]=sa[i]-w;
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=N;i++)cnt[rk[i]]++;
		for(int i=1;i<=M;i++)cnt[i]+=cnt[i-1];
		for(int i=N;i;i--)sa[cnt[rk[id[i]]]--]=id[i];
		P=0;
		memcpy(oldrk,rk,sizeof(rk));
		for(int i=1;i<=N;i++){
			if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])rk[sa[i]]=P;
			else rk[sa[i]]=++P;
		}
	}
	//求height数组 
	for(int i=1,k=0;i<=N;i++){
		if(rk[i]==N)continue;
		if(k)k--;
		while(s[i+k]==s[sa[rk[i]+1]+k])k++;
		st[rk[i]][0]=k;
	} 
	for(int i=1;i<=N;i++){//预处理属于文本串的后缀的前缀和 
		tot[i]=tot[i-1]+(sa[i]<=n);
	}
	for(int i=1;i<=20;i++){//预处理st表求LCP 
		for(int x=1;x+(1<<i)-1<N;x++){
			st[x][i]=min(st[x][i-1],st[x+(1<<i-1)][i-1]);
		}
	}
	if(!fl){//O(qm log n)
		for(int i=1;i<=q;i++){
			ll ans=0;
			for(int j=x[i];j<=y[i];j++){//暴力遍历所有查询区间 
				int L=l[j],R=r[j];
				int p=sti[i]+L,len=R-L+1;
				//p:当前查询对应的子串在总串的位置，len:LCP需要的最小长度 
				int l=1,r=rk[p];//二分合法后缀的左端点 
				while(l<r){
					int mid=(l+r)>>1;
					if(get(mid,rk[p])>=len)r=mid;
					else l=mid+1;
				}
				int al=r;
				l=rk[p],r=N;
				while(l<r){//二分合法后缀的右端点 
					int mid=(l+r+1)>>1;
					if(get(rk[p],mid)>=len)l=mid;
					else r=mid-1;
				}
				int ar=l;
				ans+=tot[ar]-tot[al-1];//统计答案 
			}
			cout<<ans<<'\n';
		}
	}
	else{//O(qk^2 log n)
		for(int i=1;i<=q;i++){
			ll ans=0;
			for(int j=0;j<k;j++){
				int lal=1,lar=N;//记录上一次二分到的端点（卡常） 
				int p=sti[i]+j;
				int mx=min(max(st[rk[p]-1][0],st[rk[p]][0]),k-j);
				for(int len=1;len<=mx;len++){//左端点为j，长度为len的查询 
					if(cntt[j][len].size()&&cntt[j][len].front()<=y[i]&&cntt[j][len].back()>=x[i]){//判断当前区间是否存在查询 
						int li=lower_bound(cntt[j][len].begin(),cntt[j][len].end(),x[i])-cntt[j][len].begin(),ri=upper_bound(cntt[j][len].begin(),cntt[j][len].end(),y[i])-cntt[j][len].begin()-1;//二分出对应的查询区间 
						if(li>ri)continue; 
						int l=lal,r=rk[p],al,ar;
						while(l<r){//二分合法后缀的左端点 
							int mid=(l+r)>>1;
							if(get(mid,rk[p])>=len)r=mid;
							else l=mid+1;
						}
						al=r;
						lal=r;
						l=rk[p],r=lar;
						while(l<r){//二分合法后缀的右端点 
							int mid=(l+r+1)>>1;
							if(get(rk[p],mid)>=len)l=mid;
							else r=mid-1;
						}
						ar=l;
						lar=l;
						ans+=(ri-li+1)*(tot[ar]-tot[al-1]);//统计答案 
					}
					
				}
			}
			cout<<ans<<'\n';
		}
	}
	return 0;
}

#include <bits/stdc++.h>
#define N 200034
#define LN 18
using namespace std;

typedef long long ll;

int n, m, q, k;
int l[N], r[N], mat[N], ver[N];
int p[LN][N];
char s[N];

vector <int> qry[513][513];

namespace SAM{
	int p, np = 1, cnt = 1;
	int pa[N], d[N][26], val[N];
	int f[N], child[N][26], cc[N];

	#define q d[p][x]
	void extend(int x){
		for(p = np, val[np = ++cnt] = val[p] + 1; p && !q; q = np, p = pa[p]);
		if(!p) pa[np] = 1;
		else
			if(val[p] + 1 == val[q]) pa[np] = q;
			else{
				int nq = ++cnt;
				val[nq] = val[p] + 1;
				memcpy(d[nq], d[q], 104);
				pa[nq] = pa[q];
				pa[np] = pa[q] = nq;
				for(int Q = q; p && q == Q; q = nq, p = pa[p]);
			}
		f[np] = 1;
	}
	#undef q

	void initBin(){
		int i, j;
		for(i = 1; i <= cnt; ++i) ::p[0][i] = pa[i];
		for(j = 0; j < LN - 1; ++j)
			for(i = 1; i <= cnt; ++i)
				::p[j + 1][i] = ::p[j][::p[j][i]];
	}

	void dfs(int x){
		for(int i = 1; i <= cc[x]; ++i){
			dfs(child[x][i]);
			f[x] += f[child[x][i]];
		}
	}

	void main(){
		int i;
		for(i = 1; i <= cnt; ++i)
			child[pa[i]][++cc[pa[i]]] = i;
		dfs(1);
	}
}

ll jump_until(int t, int v){
	for(int i = LN - 1; i >= 0; --i)
		if(SAM::val[p[i][t]] >= v) t = p[i][t];
	return SAM::f[t];
}

int main1(){
	int i, u, v, id, t, len; ll ans;
	for(i = 0; i < m; ++i) scanf("%d%d", l + i, r + i);
	SAM::initBin();
	for(; q; --q){
		scanf("%s%d%d", s, &u, &v);
		t = 1; len = 0; ans = 0;
		for(i = 0; i < k; ++i){
			id = s[i] - 'a';
			for(; t && !SAM::d[t][id]; t = SAM::pa[t], len = SAM::val[t]);
			t ? (t = SAM::d[t][id], ++len) : (t = 1, len = 0);
			mat[i] = len; ver[i] = t;
		}
		for(i = u; i <= v; ++i)
			if(mat[r[i]] > r[i] - l[i])
				ans += jump_until(ver[r[i]], r[i] - l[i] + 1);
//			printf("ans[%d] = %lld\n", i, ans);
		printf("%lld\n", ans);
	}
	return 0;
}

int main2(){
	int i, j, u, v, id, t, cnt; ll ans;
	for(i = 0; i < m; ++i){
		scanf("%d%d", &u, &v);
		qry[u][v].push_back(i);
	}
	for(; q; --q){
		scanf("%s%d%d", s, &u, &v); ans = 0;
		for(i = 0; i < k; ++i){
			t = 1;
			for(j = i; j < k; ++j){
				id = s[j] - 'a';
				if(t = SAM::d[t][id]){
					cnt = upper_bound(qry[i][j].begin(), qry[i][j].end(), v) - lower_bound(qry[i][j].begin(), qry[i][j].end(), u);
					ans += (ll)cnt * SAM::f[t];
				}else break;
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

int main(){
	int i;
	scanf("%d%d%d%d%s", &n, &m, &q, &k, s);
	for(i = 0; i < n; ++i) SAM::extend(s[i] - 'a');
	SAM::main();
	return k >= 512 ? main1() : main2();
}