No.1005 BOT対策
タグ : / 解いたユーザー数 312
作問者 :
eSeF
/ テスター :
tatyam
問題文
とあるSNSでは、投稿した文章に特定の単語が含まれていると、それに自動で反応して返信をする 'BOT' と呼ばれるアカウントが存在します。
BOTは、投稿された文章に連続部分文字列として $T$ が含まれる場合に反応します。
SFくんは文字列 $S$ として表される文章を投稿しようとしています。
SFくんはBOTに反応されたくないので、
$S$ の適当な位置に文字'.'を挿入して、BOTに反応されないようにすることにしました。
BOTに反応されなくすることが可能か判定し、可能であれば、反応されなくするために、
最小で何文字の'.'を挿入すべきか求めてください。
入力
$S$ $T$
【制約】
・$S,\ T$ は英小文字からなる長さ $1$ 以上 $1000$ 以下の文字列
出力
反応されなくなることが不可能であれば、'-1'を出力せよ。
可能ならば、挿入すべき'.'の数の最小値を出力せよ。
サンプル
サンプル1
入力
doyouknowsegmenttreeiknowsegmenttree segmenttree
出力
2
このまま投稿すると、 $S$ には連続部分文字列として"segmenttree"が含まれるので、BOTが反応してしまいます。
例えば、文字'.'を二箇所に挿入し、
$S$ を"doyouknowsegment.treeiknowsegment.tree"などとすれば良いです。
一箇所以下の挿入では反応が防げないのでこれが答えです。
サンプル2
入力
youaretouristofworldofwakingup zekki
出力
0
挿入をしなくても反応されません。
サンプル3
入力
sumomomomomomomomonouchi momo
出力
4
例えば"sumo.mom.omom.omom.omonouchi"とすると反応されません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。