B3733 [信息与未来 2017] 基因组分析

chen_zhe · 2025-03-07 17:23:12 · 题解

欢迎报名洛谷网校，期待和大家一起进步！

本题考察了字符串函数和 C++ STL 中集合（set）的应用。

首先我们根据题意，使用题目中对 R_i 的生成方式，生成 R_i。接着根据 R_i \bmod 4 的值为 0,1,2,3 时分别为 \tt{A,T,C,G} 这一句话，我们生成得到字符串 s。

基因组字符串到手后，下一步是提取所有长度为 k 的字符串。这里可以使用 substr 函数，使用方式是 string l = s.substr(i, k)，指的是从下标 i 开始截取长度为 k 的字符串，放入变量 l 中。

接着，由于题目中说到要统计有多少个不同的字符串，C++ 的 set 容器成了我们的好帮手。set 会自动去重，每次插入一个子串，它只保留唯一值。因此我们只要把截取的子串放入 set 中，最后输出集合大小即可。

参考代码（只展示关键部分）：

for (int i = 0; i < s.size() - k + 1; i++) {
    l = s.substr(i, k);
    set_gs.insert(l);
}
cout << set_gs.size() << endl;