题解：UVA10829 L-Gap Substrings

首先发现不固定长度是困难的，所以应该枚举长度。但是如果这样了，还是得枚举起始点啊，怎么办？那么尝试看看开始位置在

i\sim i+len-1

之间的能不能统一计算？

由于我脑子不好，所以先讲讲我的假做法和蒸馍修正。考虑一个 |...|...|...| 的东东，我们枚举开始位置是什么区间，考虑是 [...].[.|.].| 这种区间。那么我们发现如果这个是合法的，|[..|].[|..]| 是合法的如果下一位也是相等的。这说明啥？这说明如果

i\sim i+len-1

中发现了第一次合法的，那么从他开始有一个区间是合法的，然后又不合法了。那么我们的合法性是 xxxxoooxxxxx 这种结构的。

发现这个求出区间就是困难的事情啊。但是这种区间也是很通用的，就是所有满足的涵盖一个位置的区间也是连续的。

然后发现了一个重要的性质：所有

i\sim i+len-1

开头的区间一定涵盖

i+k-1

。那么就好做了啊！二分+哈希求出开始，结束合法位置即可。

时间复杂度

\mathcal{O}(n\log^2 n)

。

CPP

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e5+5;
const ll B = 37;
const ll mod = 998244353;

int n,k;
string s;
ll pw[N],hs[N];

ll qy(ll l,ll r){
	return (hs[r]-hs[l-1]*pw[r-l+1]%mod+mod)%mod;
}

int lcs(int a,int b){
	int l=0,r=min(a,b)+1;
	while (l+1<r){
		int mid=l+r>>1;
		if (qy(a-mid+1,a)==qy(b-mid+1,b)) l=mid;
		else r=mid;
	}
	return l;
}

int lcp(int a,int b){
	int l=0,r=n-b+2;
	while (l+1<r){
		int mid=l+r>>1;
		if (qy(a,a+mid-1)==qy(b,b+mid-1)) l=mid;
		else r=mid;
	}
	return l;
}

int tc;

void solve(){
	cin>>k>>s;
	n=s.size();
	s=" "+s;
	for (int i=1; i<=n; i++){
		hs[i]=(hs[i-1]*B%mod+s[i]-'a'+1)%mod;
	}
	ll ans=0;
	for (int l=1; l<=n; l++){
		for (int i=l; i+l+k<=n; i+=l){
			int j=i+l+k;
			if (s[i]!=s[j]) continue;
			int lb=lcs(i,j),rb=lcp(i,j);
			lb=min(lb,l);
			rb=min(rb,l);
			if (lb+rb-1>=l) ans+=lb+rb-l;
		}
	}
	cout<<"Case "<<++tc<<": "<<ans<<"\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	pw[0]=1;
	for (int i=1; i<N; i++) pw[i]=pw[i-1]*B%mod;
	int t;
	cin>>t;
	while (t--){
		solve();
	} 
	return 0;
}

题解：UVA10829 L-Gap Substrings

文章操作

相关推荐

评论

题解：UVA10829 L-Gap Substrings