MẬT KHẨU
View as PDFMuốn có được bản đồ kho báu đội tìm kiếm phải tìm được mật khẩu để mở cửa hầm bí mật. Biết rằng mật khẩu tìm được dựa vào một xâu kí tự ~S~ cho trước và việc tìm mật khẩu dựa vào định nghĩa như sau: Sự giống nhau của hai xâu ~A~ và ~B~ là chiều dài của tiền tố chung dài nhất của hai xâu đó.
Ví dụ:
Sự giống nhau của xâu abc và xâu abd là ~2~, còn sự giống nhau của xâu aaa và aab là ~2~
Vậy mật khẩu cần tìm là tổng sự giống nhau giữa các hậu tố của ~S~ so với ~S~.
Ví dụ: Cho xâu ~S = ~abcdab có các hậu tố của xâu ~S~ là abcdab , bcdab , cdab , dab , ab và b . Theo định nghĩa độ dài giống nhau của các hậu tố trên so với xâu ~S~ tương ứng là ~6, 0, 0, 0, 2, 0~. Do đó, là ~6 + 0 + 0 + 0 + 2 + 0 = 8~ chính là mật khẩu giúp đội tìm kiếm mở cửa hầm bí mật.
Bạn hãy viết chương trình giúp đội tìm kiếm tìm ra mật khẩu khi biết xâu ~S~.
Dữ liệu
Gồm một dòng chứa xâu ~S~ có độ dài không vượt quá ~10^6~ và chỉ bao gồm các chữ cái tiếng Anh thường.
Kết quả
Ghi ra một số nguyên là mật khẩu cần tìm.
Ví dụ
matkhau.inp
abcdab
matkhau.out
8
Ràng buộc
~ 1 \leq |S| \leq 10^6~
Comments
idk