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 biên của xâu

    Cho xâu SSS độ dài nnn. Một biên (border) của SSS là một xâu vừa là tiền tố thực sự (prefix, độ dài <n< n<n và >0> 0>0) vừa là hậu tố (suffix) của SSS.

    Hãy đếm số biên của SSS.

    Gợi ý: dùng hàm Z. Với mỗi vị trí i≥1i \ge 1i≥1, nếu Z[i]=n−iZ[i] = n - iZ[i]=n−i thì hậu tố bắt đầu tại iii trùng với tiền tố cùng độ dài, tức là một biên.

    Ví dụ: S=S = S= abcab có biên ab (độ dài 222), nên đáp án là 111.

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

      Một dòng chứa xâu SSS gồm các chữ cái la-tinh thường.

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

      1≤∣S∣≤1061 \le |S| \le 10^61≤∣S∣≤106.

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

      In ra một số nguyên là số biên của SSS.

    Ví dụ:

    Đầu vào:

    abcab

    Đầu ra:

    1

    Giải thích:

    Các tiền tố thực sự của abcab là a, ab, abc, abca. Trong đó chỉ ab vừa là tiền tố vừa là hậu tố. Vậy có đúng 1 biên.

    Đang tải editor...