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

    solution

    Đề bài: [C] Đếm số lần xuất hiện mẫu trong văn bản — KMP

    Cho hai chuỗi: văn bản TTT độ dài nnn và mẫu PPP độ dài mmm. Hãy đếm số vị trí TTT chứa PPP như một chuỗi con (cho phép chồng lấn).

    Dùng thuật toán KMP với mảng prefix-function failfailfail: với mỗi vị trí iii trong PPP, fail[i]fail[i]fail[i] là độ dài lớn nhất của tiền tố cũng là hậu tố của P[0..i]P[0..i]P[0..i]. Khi so khớp, dùng failfailfail để nhảy mà không quay lui TTT — tổng O(n+m)O(n + m)O(n+m).

    Ví dụ T=T = T= "aaaaa", P=P = P= "aa" → 444 vị trí.

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

      Một dòng chứa TTT và PPP cách nhau bởi dấu cách (không chứa khoảng trắng).

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

      1≤∣T∣≤1051 \le |T| \le 10^51≤∣T∣≤105, 1≤∣P∣≤1041 \le |P| \le 10^41≤∣P∣≤104. Cho phép xuất hiện chồng lấn.

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

      Một số nguyên — số lần xuất hiện.

    Ví dụ:

    Đầu vào:

    ababababab abab

    Đầu ra:

    4

    Giải thích:

    Khớp tại vị trí 0, 2, 4, 6 → 4 lần.

    Đang tải editor...