加里敦大学的生物研究所，发现了决定人喜不喜欢吃藕的基因序列 S,有这个序列的碱基序列就会表现出喜欢吃藕的性状，但是研究人员发现对碱基序列 S，任意修改其中不超过 3 个碱基，依然能够表现出吃藕的性状。现在研究人员想知道这个基因在 DNA 链 S0 上的位置。所以你需要统计在一个表现出吃藕性状的人的 DNA 序列 S0 上，有多少个连续子串可能是该基因，即有多少个 S0 的连续子串修改小于等于三个字母能够变成 S。
第一行有一个整数 T，表示有几组数据。
每组数据第一行一个长度不超过 105 的碱基序列 S0。
每组数据第二行一个长度不超过 105 的吃藕基因序列 S。
共 T 行，第 i 行表示第 i 组数据中，在 S0中有多少个与 S 等长的连续子串可能是表现吃藕性状的碱基序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| // Problem: P3763 [TJOI2017]DNA
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3763
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/SAM.h"
#include "ybwhead/ios.h"
CPTH::SAM<char> x;
string s, s1;
const char xx[5] = {'A', 'C', 'G', 'T'};
long long ans;
const int maxn = 2e5 + 10;
int cnt[maxn];
int m;
void dfs(register int u, register int len, register int pp)
{
// yout << u << " " << len << " " << pp << endl;
if (len > m)
return (void)(ans += cnt[u]);
CPTH::SAM<char>::SAMNode xxx = x[u];
for (register int i = 0; i < 4; ++i)
{
if (!xxx[xx[i]])
continue;
if (s1[len - 1] == xx[i])
dfs((int)xxx[xx[i]], len + 1, pp);
else if (pp < 3)
dfs((int)xxx[xx[i]], len + 1, pp + 1);
}
}
int main()
{
int TTT;
yin >> TTT;
while (TTT--)
{
yin >> s >> s1;
m = s1.size();
x.clear();
memset(cnt, 0, sizeof(cnt));
for (auto c : s)
cnt[x.append(c)] = 1;
// x = CPTH::SAM<>(s);
x.buildTree();
function<void(int)> dfs1 = [&](int u) {
for (auto v : x.children(u))
{
dfs1(v);
cnt[u] += cnt[v];
}
};
dfs1(0);
ans = 0;
dfs(0, 1, 0);
yout << ans << endl;
}
return 0;
}
|
v1.4.14