Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [C] Đếm chuỗi con có chồng lấp — phát hiện pattern DNA

    Trong phân tích chuỗi DNA, một pattern có thể xuất hiện chồng lấp. Cho chuỗi SSS và pattern TTT, đếm số vị trí iii trong SSS sao cho S[i..i+∣T∣−1]=TS[i..i+|T|-1] = TS[i..i+∣T∣−1]=T (cho phép chồng lấp).

    Ví dụ: SSS = aaaa, TTT = aa → 3 vị trí (0, 1, 2).

    • Định dạng đầu vào:

      Dòng 1: SSS. Dòng 2: TTT.

    • Ràng buộc đầu vào:

      ∣S∣,∣T∣≤2000|S|, |T| \le 2000∣S∣,∣T∣≤2000.

    • Định dạng đầu ra:

      Một số nguyên.

    Ví dụ:

    Đầu vào:

    aaaa
aa

    Đầu ra:

    3

    Giải thích:

    Vị trí 0, 1, 2 đều khớp → 3.

    Đang tải editor...