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

    solution

    Đề bài: [Giải thuật] Đếm số lần xuất hiện mẫu bằng Z-function

    Cho mẫu ppp và văn bản ttt (ký tự a–z). Đếm số vị trí trong ttt mà ppp xuất hiện (các lần xuất hiện được phép chồng lấn). Sử dụng hàm Z trên xâu ghép p+# ⁣+tp + \#\!+ tp+#+t.

    Ví dụ p=aap=\texttt{aa}p=aa, t=aaaat=\texttt{aaaa}t=aaaa thì ppp xuất hiện 333 lần (vị trí 0,1,20,1,20,1,2).

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

      Dòng 1: mẫu ppp. Dòng 2: văn bản ttt.

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

      1≤∣p∣≤∣t∣≤2⋅1051 \le |p| \le |t| \le 2\cdot10^51≤∣p∣≤∣t∣≤2⋅105.

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

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

    Ví dụ:

    Đầu vào:

    aa
aaaa

    Đầu ra:

    3

    Giải thích:

    Mẫu `aa` khớp tại vị trí 0,1,2 của `aaaa` (cho phép chồng lấn) nên đáp án 3.

    Đang tải editor...