問題文

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

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

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

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

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

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

入力

入力は以下の形式で標準入力から与えられる。

$S$ $K$

• $1$ 行目には、入力したい文字列 $S (1 ≦ |S| ≦ 50)$ が、$1$ 行で与えられる。文字列 $S$ は、小文字アルファベットまたは数字のみで構成されていることが保障されてます。
• $2$ 行目には、高橋君が覚えているキーの種類を表す文字列 $K$ が、$1$ 行で与えられる。文字列 $K$ は、1234567890abcdefghijklmnopqrstuvwxyz から、$1$ つの文字を選んで削除する操作を任意の回数行うことで作成可能な文字列であり、先頭文字が1であることが保障されている。

出力

高橋君がキーを叩く必要のある回数の期待値を $1$ 行で出力せよ。出力の末尾は改行をいれること。

出力は絶対誤差または相対誤差が $10^{-6}$ 以下であれば許容される。

入力例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$ です。

Source Name

Code Formula 2014 予選A