【CCPC2023深圳】相似基因序列问题

题目传送门

https://cpc.csgrandeur.cn/csgoj/problemset/problem?pid=1243

思路

K=0

对于每个字符串求出它的哈希值，$O(nq)$ 两两比对就好

K=1

这是一个经典的二分+哈希问题。

考虑这样两个字符串
$s1=abcabcabcabc$
$s2=abcabaabcabc$
分别令$pre1[i]$和$pre2[i]$为$s1,s2$的前缀
可以发现当$i\le 5$时，$pre1[i]=pre2[i]$
但是当$i>5$时，$pre1[i]\ne pre2[i]$
也就说，$i$越小，前缀越容易相等，当$i$大于某个值，前缀就不再相等了。
也就说最大的$i$具有可二分性
于是我们二分$i_{max}$，用哈希判断二分出的前缀是否相等。
那么$s1,s2$会在$i_{max}+1$不相同
之后判断$i_{max}+2$后面的部分是否相等即可。
时间复杂度$O(nqlogm)$

K>1

考虑这样一组数据
$K=2$
$s1=aabaacaa$
$s2=aaaaccaa$
按照$K=1$的做法，我们可以二分出$i_{max}=2$
于是$s1,s2$在$i=3$的位置失配（不一样）了。可以理解为消耗了一次失配的机会。

显然，前面的东西我们已经考虑过了，对后面的答案不会有影响了，所以这组数据等价于
$K=1$
$s{1}^{\prime }=aacaa$
$s{2}^{\prime }=accaa$
于是又回到了$K=1$的情况

可以发现，一个失配的位置就会把字符串分成两段，同时消耗一次失配的机会(K-1)
那么$K$个失配的位置就会吧字符串分成$K+1$段
所以我们进行$K+1$次二分，判断最后一次的$i_{max}$是否等于$m$即可
时间复杂度$O(nqKlogm)$

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=307,M=60007,p=19260817,mod=1e9+7;
int a[N];
vector<int> hs[N];
vector<int> h,_p;
int m;
bool Hash(int l,int r,int i)
{
	int hs1=(hs[i][r]-hs[i][l-1]+mod)*_p[m-r]%mod;
	int hs2=(h[r]-h[l-1]+mod)*_p[m-r]%mod;
	return hs1==hs2;
}
void init(int m)
{
	_p.resize(m+1);
	_p[0]=1;
	for(int i=1; i<=m; i++) _p[i]=_p[i-1]*p%mod;
}
void O_o()
{
	int n,q,k;
	string s;
	cin>>n>>q>>m>>k;
	init(m);
	for(int i=1; i<=n; i++)
	{
		cin>>s;
		int j=0;
		hs[i].resize(m+1);
		for(auto c:s)
		{
			j++;
			hs[i][j]=(hs[i][j-1]+c*_p[j-1])%mod;
		}
	}
	while(q--)
	{
		int ans=0;
		cin>>s;
		h.resize(m+1);
		int j=0;
		for(auto c:s)
		{
			j++;
			h[j]=(h[j-1]+c*_p[j-1])%mod;
		}
		for(int i=1; i<=n; i++)
		{
			int t=k;
			bool bz=0;
			int las=0;
			while(t>=0&&!bz)
			{
				int l=las+1,r=m,ass=m+1;
				while(l<=r)
				{
					int mid=l+r>>1;
					if(Hash(l,mid,i))
					{
						l=mid+1;
					}
					else
					{
						ass=mid;
						r=mid-1;
					}
				}
				if(ass==m+1)
				{
					bz=1;
					break;
				}
				las=ass;
				t--;
			}
			ans+=bz;
		}
		cout<<ans<<"\n";
	}
}
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cout<<fixed<<setprecision(2);
	int T=1;
//	cin>>T;
	while(T--)
	{
		O_o();
	}
}