Module: ハッシュ


Problem

2 /2


ハッシュ

Theory Click to read/hide

文字列のハッシュ化は、文字列ごとに一意の数値として文字列を表現することです (衝突の可能性は無視できると仮定します)。これにより、重要なデータ (パスワードなど) を文字列ではなく数値としてデータベースに保存できます。これにより、攻撃者がパスワード データベースにアクセスした場合にパスワードを保護できます。攻撃者はパスワード自体を取得するのではなく、数値表現のみを取得し、ハッシュによって文字列を取得することはほとんど不可能であるためです (特にハッシュ アルゴリズムを知らなければ)。 ). 
多項式ハッシュは、プログラミング競技の問題で最もよく使用されます。
文字列 S のハッシュ関数を決定する最良の方法の 1 つは次のとおりです。
h(S)  =  S[0]  +  S[1] * P  +  S[2] * P^2  +  S[3] * P^3  +  ...  +  S[N] * P^N

Problem

プログラマーの Vasya は不運でした。休暇の代わりに、科学会議に出張することになりました。 「知識のレベルを高める必要がある。暗号に関する重要な会議がフランスで開催されている。そこで彼らはリシュリューの時代に暗号化し、ビエタの時代に他人の暗号を解読した。」と上司は語った。
ヴァシャは、ルーブル美術館の絵画をすべてどこかですでに見ていることにすぐに気づきました。ネズミが敷物からエッフェル塔を拭き取る前から、エッフェル塔の光景は彼にとって退屈になりました。私たちはあらゆる種類のキオスクや売店向けにこのようなガラスのピラミッドを作っています。怪しい飲食店。一言で言えば、パリには見るものは何もなく、釣りをする場所もなかったため、ヴァシャは会議の報告に出席しなければならなかった。
講演者の 1 人は、ベーコンの暗号を再び解明しようとして、ベーコンの作品の考えられるすべての部分文字列を分析することで、ベーコンの謎の鍵を見つけることができるという仮説を提唱しました。 「でも、数が多すぎるよ！」ヴァシャは大声で驚いた。 「いえ、それほどではありません！」 - 講演者は叫びました、 - 「計算してみろ、そうすれば自分の目でわかるだろう！」
同じ夜、ヴァシャはインターネットでベーコンの全作品を見つけました。彼はテキストを 1 つの長い行に変換し、テキストからすべてのスペースと句読点を削除するプログラムを作成しました。そして今、Vasya は非常に困惑しています - この文字列の異なる部分文字列の数をどうやって数えればよいでしょうか? 

入力
入力には、Vasya が受信した空ではない文字列が含まれています。文字列は小文字のラテン文字のみで構成されます。長さは 2000 文字を超えてはなりません。

出力
この文字列の異なる部分文字列の数を出力します。

 

例
<頭> <本体>

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!

# 入力 出力
1 あば 8