自动搬运

查看原文

来自洛谷，原作者为

	Stars_visitor_tyw INFP-T||小亭繁花依旧 岁月悄乘南风

搬运于2025-08-24 21:52:27，当前版本为作者最后更新于2024-06-21 17:15:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P3763 [TJOI2017] DNA 题解

分析

模拟赛没细想打了暴力。

暴力思路就是枚举起点以及遍历 $s$，按题意判断，优化一下可以拿 $60$ 分。

暴力代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
//	freopen("T4.in","r",stdin);
//	freopen("T4.out","w",stdout);
	ios::sync_with_stdio(0);
	int t;
	for(cin>>t;t;t--)
	{
		string a, b;
		cin>>a>>b;
		int n=a.size(), m=b.size();
		a=" "+a;
		b=" "+b;
		int ans=0;
		for(int i=1;i<=n-m+1;i++)
		{
			int cnt=0;
			for(int j=1;j<=m;j++)
			{
				if(a[i+j-1]!=b[j])
				{
					cnt++;
				}
				if(cnt>3)break;//优化
			} 
			if(cnt<=3)
			{
				ans++;
			}
		}
		cout<<ans<<"\n";
	} 
	return 0;
}

接下来说正解。个人认为这是最通俗易懂的解法。

可以发现暴力程序主要是在比对的时候花的时间太长了。考虑进一步优化。

作为提高组选手，看到比对字符串很容易就想到哈希。

我们尝试比对出前三个不同的地方，最后一段如果能匹配上就是一个答案，反之则不是。当然如果还没找到三处不同就已经匹配完整个 $s$ 串了，那么这也是一个答案。

细细思考一下，容易发现哈希的匹配具有单调性，具体来讲，如果两个字符串的前 $l$ 个字符可以匹配上，那么前 $l-1$ 个字符也可以匹配上；如果两个字符串的前 $l$ 个字符不能匹配上，那么前 $l+1$ 个字符也不能匹配上。

考虑二分，二分出前三个不同的地方，如果匹配完了就结束二分并累加答案，否则判断剩余部分是否匹配即可。

正确代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
unsigned long long hs[N], pw[N], ht[N], base=19991;
unsigned long long get_hash(unsigned long long hsd[], int lt, int rt)
{
	return hsd[rt]-hsd[lt-1]*pw[rt-lt+1];
}
bool check(int l, int ed)
{
	int st=1, r=l+ed-1;
	for(int i=1;i<4;i++)
	{
		int lt=-1, rt=ed-st+2;
		while(lt+1<rt)
		{
			int mid=(lt+rt)>>1;
			if(get_hash(hs,l,l+mid-1)==get_hash(ht,st,st+mid-1))lt=mid;
			else rt=mid;
		}
		l+=lt+1;
		st+=lt+1;
		if(st>ed)return 1;
	}
	return get_hash(hs,l,r)==get_hash(ht,st,ed);
}
int work()
{
	string s0, s;
	cin>>s0>>s;
	if(s0.size()<s.size())return 0;
	int len1=s0.size(),len2=s.size();
	s0=" "+s0;
	s=" "+s;
	for(int i=1;i<=len1;i++)hs[i]=hs[i-1]*base+s0[i];
	for(int i=1;i<=len2;i++)ht[i]=ht[i-1]*base+s[i]; 
	int ans=0;
	for(int i=1;i+len2-1<=len1;i++)
	{
		if(check(i,len2))ans++;
	}
	return ans;
} 
signed main()
{
	pw[0]=1;
	for(int i=1;i<=100000;i++)pw[i]=pw[i-1]*base;
	int t;
	for(cin>>t;t;t--)cout<<work()<<"\n";
}