Đề bài
Các phòng giám định pháp y so sánh người với nhau dựa vào các đoạn lặp ngắn liền kề (short tandem repeat, STR): những đơn vị DNA ngắn như AGAT xuất hiện nhiều lần liên tiếp. Với mỗi đơn vị, phòng thí nghiệm ghi lại số bản sao liên tiếp nhiều nhất ở bất kỳ đâu trong chuỗi. Trong TTAGATAGATAGATCAGATAGAT, đơn vị AGAT lặp ba lần liên tiếp gần đầu chuỗi và hai lần ở phía sau, nên số đếm của nó là 3.
Hãy viết dna_str_count(sequence, repeats).
Đầu vào
sequence: Chuỗi DNA, chỉ gồm các chữ cái A, C, G và T.
repeats: Các đơn vị STR cần đo.
Đầu ra
Trả về một số đếm cho mỗi đơn vị, theo đúng thứ tự trong repeats: số bản sao nối tiếp nhau nhiều nhất. Đơn vị nào không xuất hiện thì có số đếm 0.
Ràng buộc
0 ≤ độ dài sequence ≤ 5,000
1 ≤ số đơn vị ≤ 10
Mỗi đơn vị có từ 1 đến 8 chữ cái
Ví dụ
Đầu vào:
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]
Kết quả mong đợi:
expected = [3, 1]
Đầu vào:
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};
Kết quả mong đợi:
std::vector<long long> expected = {3, 1};
Đầu vào:
string sequence = "TTAGATAGATAGATCAGATAGAT";
string[] repeats = new string[] {"AGAT", "CA"};
Kết quả mong đợi:
long[] expected = new long[] {3, 1};
Giải thích
AGAT lặp 3 lần ở đầu và chỉ 2 lần ở cuối nên được 3; CA xuất hiện một lần nên được 1.
Đầu vào:
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]
Kết quả mong đợi:
expected = [3, 1, 0]
Đầu vào:
std::string sequence = "AATGAATGAATGTATC";
std::vector<std::string> repeats = {"AATG", "TATC", "GATA"};
Kết quả mong đợi:
std::vector<long long> expected = {3, 1, 0};
Đầu vào:
string sequence = "AATGAATGAATGTATC";
string[] repeats = new string[] {"AATG", "TATC", "GATA"};
Kết quả mong đợi:
long[] expected = new long[] {3, 1, 0};
Giải thích
AATG lặp 3 lần, TATC một lần và GATA không lần nào: [3, 1, 0].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Từ một vị trí bắt đầu, cứ nhảy tới một đoạn bằng độ dài đơn vị chừng nào đoạn tiếp theo còn trùng với đơn vị.
Gợi ý 2
Thử mọi vị trí bắt đầu và ghi nhớ dãy dài nhất.
Gợi ý 3
Đơn vị nào không khớp lần nào thì số đếm tốt nhất vẫn là 0.
Độ phức tạp mong đợi
thời gian O(n × m × k), bộ nhớ phụ O(m)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.