1243 : 相似基因序列问题

Description

【题目背景】

生物的遗传物质存在个体间或种群水平的差异，这样的差异被称为遗传变异。突变及基因重组等因素都会导致遗传变异。尽管亲代在将其遗传信息传递给子代时会发生遗传变异，但是这些遗传变异仅占遗传物质的一小部分，通常亲代和子代之间的遗传物质非常相似。遗传变异会在生物繁殖的过程中不断累积。通过比较不同生物的基因特征及基因组结构，可以大致确定生物之间的亲缘关系，并建立系统进化树。在比较过程中，可能有一些遗传物质的子序列完全相同或相似，我们称这种序列为保守序列。

假设现在已经测定了若干以 DNA 为遗传物质的生物的 DNA 碱基序列，希望通过比较这些基序列推测生物之间的亲缘关系。为了简化比较，先将碱基序列划分为若干个保守序列片段。考虑到 DNA 序列可能发生缺失、插入等影响片段数量的遗传变异，将划分得到的片段对齐至 \(M\) 个片段，并使用小写字母来表示对齐后的每一个片段。

【题目描述】

已知一棵包含了 \(N\) 个生物的系统进化树，这些生物的 DNA 序列对应的对齐至 \(M\) 个片段的序列可以用仅含小写字母的字符串表示为 \(s_1, \dots,s_N\)。在这棵系统进化树上，如果两个生物对应的序列最多只有 \(K\) 处对应位置上的片段不相同（即对应字母不同），就称这两个生物的亲缘关系相近。

现有 \(Q\) 个尚未确定亲缘关系的生物，对齐得到序列分别为 \(t_1, \dots,t_Q\)。为了确定这些生物在系统进化树上的位置，请对 \(Q\) 个生物分别求出，原树中有多少个生物与其亲缘关系相近。

Input

输入的第一行包含四个正整数 \(N, Q, M, K\)，分别表示系统进化树上的生物数量、待确定亲缘关系的生物数量、对齐后的序列长度和比较序列时容许的最大差异数。保证 \(1\le N, Q\le 300\)，\(1\le M\le 60,000\)，\(1\le K\le 10\)。

接下来 \(N\) 行，每行输入一个长度恰好为 \(M\)，仅包含小写字母的字符串 \(s_i\)，表示系统进化树上的每个生物对应的模板序列。

接下来 \(Q\) 行，每行输入一个长度恰好为 \(M\)，仅包含小写字母的字符串 \(t_j\)，表示待确定亲缘关系的每个生物对应的查询序列。

保证输入的两个字符串均仅包含小写字母。

Output

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

Sample

6 4 4 1
kaki
kika
manu
nana
tepu
tero
kaka
mana
teri
anan

##CASE##
8 6 7 3
delphis
aduncus
peronii
plumbea
clymene
hectori
griseus
electra
delphis
helpiii
perphii
clumeee
eleelea
ddlpcus

2
2
1
0

##CASE##
1
1
2
2
1
2

Hint

Source

Author

THU