相似基因序列问题 ——查找

【题目背景】

生物的遗传物质存在个体间或种群水平的差异，这样的差异被称为遗传变异。突变及基因重组等因素都会导致遗传变异。尽管亲代在将其遗传信息传递给子代时会发生遗传变异，但是这些遗传变异仅占遗传物质的一小部分，通常亲代和子代之间的遗传物质非常相似。遗传变异会在生物繁殖的过程中不断累积。通过比较不同生物的基因特征及基因组结构，可以大致确定生物之间的亲缘关系，并建立系统进化树。在比较过程中，可能有一些遗传物质的子序列完全相同或相似，我们称这种序列为保守序列。
假设现在已经测定了若干以 DNA 为遗传物质的生物的 DNA 碱基序列，希望通过比较这些基序列推测生物之间的亲缘关系。为了简化比较，先将碱基序列划分为若干个保守序列片段。考虑到 DNA 序列可能发生缺失、插入等影响片段数量的遗传变异，将划分得到的片段对齐至 M 个片段，并使用小写字母来表示对齐后的每一个片段。

【题目描述】

已知一棵包含了 N 个生物的系统进化树，这些生物的 DNA 序列对应的对齐至 M 个片段的序列可以用仅含小写字母的字符串表示为 1,…,s1,…,sN 。在这棵系统进化树上，如果两个生物对应的序列最多只有 K 处对应位置上的片段不相同（即对应字母不同），就称这两个生物的亲缘关系相近。
现有 Q 个尚未确定亲缘关系的生物，对齐得到序列分别为 1,…,t1,…,tQ 。为了确定这些生物在系统进化树上的位置，请对 Q 个生物分别求出，原树中有多少个生物与其亲缘关系相近。

Input
输入的第一行包含四个正整数 N,Q,M,K，分别表示系统进化树上的生物数量、待确定亲缘关系的生物数量、对齐后的序列长度和比较序列时容许的最大差异数。保证 1≤N,Q≤300，1≤M≤60,000，1≤K≤10。
接下来 N 行，每行输入一个长度恰好为 M，仅包含小写字母的字符串 si ，表示系统进化树上的每个生物对应的模板序列。
接下来 Q 行，每行输入一个长度恰好为 M，仅包含小写字母的字符串 tj ，表示待确定亲缘关系的每个生物对应的查询序列。
保证输入的两个字符串均仅包含小写字母。

Output
输出共 Q 行，其中第 j 行输出一个非负整数，表示在系统进化树上与第 j 个待确定的生物亲缘关系相近的生物数量。

样例输入1 
6 4 4 1
kaki
kika
manu
nana
tepu
tero
kaka
mana
teri
anan

样例输出1
2
2
1
0

样例输入2
8 6 7 3
delphis
aduncus
peronii
plumbea
clymene
hectori
griseus
electra
delphis
helpiii
perphii
clumeee
eleelea
ddlpcus

样例输出2
1
1
2
2
1
2

解析：
因为k很小，所以我们可以直接暴力枚举匹配串，然后用字符串哈希加二分暴力往前跳到不匹配的地方 k次就可以了。

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int N=100010,P=131;
ULL h[310][N]; //表示系统进化树上每个生物字符串的哈希值
ULL h1[N];     //表示待确定亲缘关系的生物字符串的哈希值
ULL p[N];
int n,q,m,k;
string s;
ULL find1(int i,int l,int r)  //返回h[i]字符串中l到r的哈希值
{
    return h[i][r]-h[i][l-1]*p[r-l+1];
}
ULL find2(int l,int r)    //返回字符串中l到r的哈希值
{
    return h1[r]-h1[l-1]*p[r-l+1];
}
bool check(int i,int l,int r)
{
    return find1(i,l,r)==find2(l,r);   
}
int main()
{
    ios;
    cin>>n>>q>>m>>k;
    p[0]=1;
    for (int i=1;i<N;i++) p[i]=p[i-1]*P;
    for (int i=0;i<n;i++)
    {
        cin>>s;
        for (int j=1;j<=s.size();j++) h[i][j]=h[i][j-1]*P+s[j-1];
    }
    while (q--)
    {
        cin>>s;
        for (int i=1;i<=s.size();i++) h1[i]=h1[i-1]*P+s[i-1];
        int ans=0;
        for (int i=0;i<n;i++)
        {
            int now=0;
            for (int j=1;j<=m;j++) 
            {
                if (!check(i,j,j))
                {
                    if (++now>k) break;
                }
                else 
                {
                    int l=j,r=m;
                    while (l<r)       //二分，快速找到下一处不匹配的位置
                    {
                        int mid=l+r+1>>1;
                        if (check(i,l,mid)) l=mid;
                        else r=mid-1;
                    }
                    j=l;             //返回不匹配的位置
                }
            }
            if (now<=k) ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}