問題文

高橋君は、無刻印キーボードが大好きです。 今日も、アルファベットと数字のみがキートップに書かれていないキーボードで、文章を書こうとしています。

しかし、高橋君は、キーボードのレイアウトを完全に覚えていません。 キーを覚えている文字は、その文字に対応するキーをそのまま叩けば良いですが、覚えていない分は、適当に選んで叩き、間違っていた場合は、バックスペースキーで削除しなくてはなりません。

高橋君は、文章 S を入力しようとしています。この文章を入力するために、キーを叩く回数の期待値を出来るだけ減らしたいです。高橋君は、どのキーを打った時にどの文字が出てきたかを記憶することが可能で、その情報を元に、次にどのキーを叩くか選択することが可能です。

高橋君が、上記目的を達成するために最適な戦略を取った時、キーを叩く回数の期待値を答えなさい。

なお、バックスペースキーの位置や、アルファベットや数字以外のキーは、全て覚えているものとします。

また、矢印キーやマウス操作などの、入力位置を変えるような操作は出来ないものとします。

入力例1

takahashikun
1234567890abcdefghijklmnopqrstuvwxyz

出力例1

12

高橋君は、全てのキーを記憶しています。 よって、キーを叩かなければいけない回数は、takahashikun の文字数と同じ 12 回です。

入力例2

p
1234567890abcdefghijklmnorstuvwxyz

出力例2

2

高橋君は、pおよびqの 2 つのキーの位置がわからなくなってしまっています。 pと打つためには、このわからない 2 つのキーのうち、どちらか 1 つを押す必要があります。

• p を押したとき、文章が完成するので、高橋君が押すキーの数の合計は 1 です。
• q を押したとき、もう 1 つのキーがpであることが解ります。よって、バックスペースキーで 1 文字を消し、もう一度pキーを押すことで、文章が完成します。この時、高橋君がキーを押した回数は 3 回になります。

以上が等確率で選ばれるので、キーを押す回数の期待値は 2 です。