Module: Băm


Problem

2 /2


Băm

Theory Click to read/hide

Băm chuỗi là biểu diễn của một chuỗi dưới dạng một số, duy nhất (chúng ta sẽ giả định rằng khả năng xảy ra xung đột là không đáng kể) cho mỗi chuỗi. Điều này cho phép bạn lưu trữ bất kỳ dữ liệu quan trọng nào (như mật khẩu) trong cơ sở dữ liệu không phải dưới dạng chuỗi mà dưới dạng số. Điều này cho phép bạn bảo vệ mật khẩu nếu kẻ tấn công giành được quyền truy cập vào cơ sở dữ liệu mật khẩu, bởi vì anh ta sẽ không tự lấy mật khẩu mà chỉ lấy biểu diễn số của chúng và gần như không thể lấy được chuỗi bằng hàm băm của nó (đặc biệt là nếu không biết thuật toán băm ). 
Băm đa thức thường được sử dụng nhiều nhất trong các bài toán cạnh tranh lập trình.
Một trong những cách tốt nhất để xác định hàm băm của chuỗi S như sau:
h(S)  =  S[0]  +  S[1] * P  +  S[2] * P^2  +  S[3] * P^3  +  ...  +  S[N] * P^N

Problem

Lập trình viên Vasya đã không may mắn - thay vì một kỳ nghỉ, anh ấy được cử đi công tác để tham dự một hội nghị khoa học. “Chúng ta cần nâng cao trình độ kiến ​​thức,” ông chủ nói, “Một hội nghị quan trọng về mật mã đang được tổ chức ở Pháp - và ở đó họ đã mã hóa vào thời Richelieu và bẻ khóa mật mã của người khác vào thời Vieta.”
Vasya nhanh chóng phát hiện ra rằng anh ấy đã nhìn thấy tất cả các bức tranh của Louvre ở đâu đó, cảnh tượng Tháp Eiffel trở nên nhàm chán với anh ấy ngay cả trước khi con chuột lau nó khỏi tấm thảm, và chúng tôi tạo ra những kim tự tháp bằng kính như vậy cho đủ loại ki-ốt và quán ăn đáng ngờ. Nói một cách dễ hiểu, đơn giản là không có gì để xem ở Paris, không có nơi nào để câu cá nên Vasya phải tham gia báo cáo tại hội nghị.
Một trong những diễn giả, một lần nữa cố gắng làm sáng tỏ các mật mã của Bacon, đưa ra giả thuyết rằng có thể tìm thấy chìa khóa cho những bí ẩn của Bacon bằng cách phân tích tất cả các chuỗi con có thể có trong các tác phẩm của Bacon. "Nhưng có quá nhiều người trong số họ!" Vasya ngạc nhiên thành tiếng. "Không, không nhiều lắm!" - người nói hét lên, - "Hãy tính toán, và bạn sẽ tự mình thấy!"
Buổi tối hôm đó, Vasya tìm thấy toàn bộ tác phẩm của Bacon trên Internet. Anh ấy đã viết một chương trình chuyển đổi văn bản thành một dòng dài, loại bỏ tất cả khoảng trắng và dấu chấm câu khỏi văn bản. Và bây giờ Vasya đang rất bối rối - làm thế nào để đếm số chuỗi con khác nhau của chuỗi này? 

Đầu vào
Đầu vào chứa một chuỗi không trống mà Vasya nhận được. Chuỗi chỉ bao gồm các ký tự Latinh viết thường. Độ dài của nó không vượt quá 2000 ký tự. 

Đầu ra
In ra số chuỗi con khác nhau của chuỗi này.

 

Ví dụ
<đầu>

time 2000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Đầu vào Đầu ra
1 aaba 8