Module: Hash'ler


Problem

2 /2


DOĞRAMAK

Theory Click to read/hide

Bir dizgeyi karma hale getirmek, bir dizgenin her bir dizi için benzersiz (çarpışma olasılığının önemsiz olduğunu varsayacağız) bir sayı olarak temsilidir. Bu, herhangi bir önemli veriyi (şifreler gibi) veritabanında dizeler olarak değil, sayılar olarak saklamanıza olanak tanır. Bu, bir saldırgan parola veritabanına erişim kazanırsa parolaları korumanıza olanak tanır, çünkü parolaların kendisini değil, yalnızca sayısal gösterimini alacaktır ve bir diziyi karma değeriyle elde etmek neredeyse imkansızdır (özellikle karma algoritmasını bilmeden) ). 
Polinom hash'leri en çok yarışma problemlerini programlamada kullanılır.
S dizisinin hash fonksiyonunu belirlemenin en iyi yollarından biri şu şekildedir:
h(S)  =  S[0]  +  S[1] * P  +  S[2] * P^2  +  S[3] * P^3  +  ...  +  S[N] * P^N

Problem

Programcı Vasya şanssızdı - tatil yerine bilimsel bir konferansa iş gezisine gönderildi. "Bilgi düzeyini artırmamız gerekiyor," dedi patron, "Fransa'da kriptografi üzerine önemli bir konferans düzenleniyor - ve orada Richelieu zamanında şifrelenmişler ve Vieta zamanında diğer insanların şifrelerini kırmışlar."
Vasya, Louvre'un tüm resimlerini bir yerlerde zaten gördüğünü çabucak anladı, Eyfel Kulesi'nin görüntüsü fare onu halıdan silmeden önce bile ona sıkıcı gelmeye başladı ve biz her türlü büfe için bu tür cam piramitler yapıyoruz ve şüpheli lokantalar Kısacası, Paris'te görülecek hiçbir şey yoktu, balık tutulacak hiçbir yer yoktu, bu nedenle Vasya'nın konferanstaki raporlara katılması gerekiyordu.
Konuşmacılardan biri, bir kez daha Bacon'ın şifrelerini çözmeye çalışırken, Bacon'ın gizemlerinin anahtarının, Bacon'ın eserlerinin olası tüm alt dizilerini analiz ederek bulunabileceği hipotezini öne sürdü. "Ama onlardan çok var!" Vasya yüksek sesle şaşırdı. "Hayır, o kadar değil!" - konuşmacıya bağırdı, - "Hesaplayın, kendiniz göreceksiniz!"
Aynı akşam Vasya, Bacon'ın tüm eserlerini internette buldu. Metinleri tek bir uzun satıra dönüştüren, metinlerdeki tüm boşlukları ve noktalama işaretlerini kaldıran bir program yazdı. Ve şimdi Vasya'nın kafası çok karışık - bu dizinin farklı alt dizilerinin sayısı nasıl hesaplanır? 

Giriş
Giriş, Vasya tarafından alınan boş olmayan bir dizi içeriyor. Dize yalnızca küçük Latin karakterlerinden oluşur. Uzunluğu 2000 karakteri geçmez. 

Çıktı
Bu dizgenin farklı alt dizilerinin sayısını yazdır.

 

Örnekler

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!

# Girdi Çıktı
1 aaba 8