Chuỗi DNA lặp lại trong C++

Cho một chuỗi DNA gồm các ký tự 'A', 'C', 'G', 'T'. Tìm tất cả các chuỗi con độ dài 10 xuất hiện nhiều hơn một lần.

Ví dụ: "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" → ["AAAAACCCCC", "CCCCCAAAAA"].

Thuật toán giải quyết (Mã hóa bit + Hash set)

Mỗi ký tự được mã hóa 2 bit: A=00, C=01, G=10, T=11. Chuỗi 10 ký tự = 20 bit, vừa trong int.

1. Khởi tạo: mảng kết quả ret, n = s.size(), hai unordered_set<int> visited, visited2, map bitVal ánh xạ ký tự → giá trị.
2. mask = 0.
3. Duyệt chuỗi:
   • mask = (mask << 2) | bitVal[s[i]].
   • mask &= 0xFFFFF (giữ 20 bit thấp).
   • Nếu i < 9 → tiếp tục.
   • Nếu mask đã có trong visited nhưng chưa có trong visited2:
     • Thêm chuỗi con s.substr(i-9, 10) vào ret.
     • Thêm mask vào visited2.
   • Thêm mask vào visited.
4. Trả về ret.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<auto> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> ret;
        int n = s.size();
        unordered_set<int> visited, visited2;
        unordered_map<char, int> bitVal = {{'A',0}, {'C',1}, {'G',2}, {'T',3}};
        int mask = 0;
        for (int i = 0; i < n; i++) {
            mask = ((mask << 2) | bitVal[s[i]]) & 0xFFFFF;
            if (i < 9) continue;
            if (visited.count(mask) && !visited2.count(mask)) {
                ret.push_back(s.substr(i - 9, 10));
                visited2.insert(mask);
            }
            visited.insert(mask);
        }
        return ret;
    }
};

int main() {
    Solution ob;
    print_vector(ob.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"));
}

Đầu vào

"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Đầu ra

[AAAAACCCCC, CCCCCAAAAA, ]