题解：P3763 [TJOI2017] DNA

· · 题解

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";
}