相似基因序列问题 ——查找
【题目背景】
生物的遗传物质存在个体间或种群水平的差异，这样的差异被称为遗传变异。突变及基因重组等因素都会导致遗传变异。尽管亲代在将其遗传信息传递给子代时会发生遗传变异，但是这些遗传变异仅占遗传物质的一小部分，通常亲代和子代之间的遗传物质非常相似。遗传变异会在生物繁殖的过程中不断累积。通过比较不同生物的基因特征及基因组结构，可以大致确定生物之间的亲缘关系，并建立系统进化树。在比较过程中，可能有一些遗传物质的子序列完全相同或相似，我们称这种序列为保守序列。
假设现在已经测定了若干以 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;
}