AtCoder Regular Contest 024

C - だれじゃ


Time limit時間制限 : 3sec / Memory limitメモリ制限 : 256MB

問題文

Takahashi 市の住人はダジャレが大好きであり、Takahashi 市で上手に渡り歩くためには高度なダジャレ能力が要求される。

Takahashi 市の住人の間では、引っ越してきた相手に様々なダジャレを浴びせることが習慣となっている。最近の Takahashi 市では「アナグラムダジャレ」というものが流行っている。「アナグラムダジャレ」とは、文章の中に、互いに共通部分を持たない、2 つの同じ長さの文字列に関して、一方に出てくる文字列を並べ替えると他方の文字列になるというものである。その文字列の長さが m であるとき、この文章は長さ m の「アナグラムダジャレ」を含むと呼ぶことにする。

例えば、「だじゃれをいったのはだれじゃ」という文章を考えると、先頭 4 文字からなる文字列「だじゃれ」と末尾 4 文字からなる文字列「だれじゃ」は互いに共通部分を持たず、かつ「だじゃれ」を並べ替えると「だれじゃ」になるため、この文章は長さ 4 の「アナグラムダジャレ」を含むということになる。

Takahashi 市に引っ越したばかりの青木君は、Takahashi 市で上手に渡り歩くために、「アナグラムダジャレ」検知能力を身につけたいと考えている。青木君は長さ K の「アナグラムダジャレ」を発見するのが苦手なので、文章生成ソフトを用いて特訓することにした。

ところが文章生成ソフトには長さ K の「アナグラムダジャレ」が含まれているか判定する機能がついていない。

あなたは青木君のために長さ K の「アナグラムダジャレ」が含まれているかを判定するプログラムを作らなければならない。


入力

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

N K
S
  • 1 行目には、与えられる文章の長さ N (1 ≦ N ≦ 10^5) および 求めたい「アナグラムダジャレ」の長さ K (1 ≦ K ≦ N) が空白区切りで与えられる。
  • 2 行目には、判定したい文章が与えられる。この文章は長さ N で、半角の小文字英字のみからなる。

部分点

この問題には部分点が設定されている。

  • N ≦ 8 を満たすデータセット 1 に正解した場合は、15 点が与えられる。
  • N ≦ 300 を満たすデータセット 2 に正解した場合は、上記とは別に 15 点が与えられる。
  • N ≦ 5,000 を満たすデータセット 3 に正解した場合は、上記とは別に 15 点が与えられる。
  • 追加制約のないデータセット 4 に正解した場合は、上記とは別に 55 点が与えられる。

出力

長さ K の「アナグラムダジャレ」が含まれるなら YES を、含まれないなら NO1 行に出力せよ。出力の末尾に改行を入れること。


入力例1

8 3
abcdbcae

出力例1

YES

先頭から 1 文字目を起点とした 3 文字からなる文字列 abc と、先頭から 5 文字目を起点とした 3 文字からなる文字列 bca は、一方を並べ替えると他方になるので、長さ 3 の「アナグラムダジャレ」を含むといえる。


入力例2

7 4
abcdcba

出力例2

NO

先頭から 1 文字目を起点とした 4 文字からなる文字列 abcd と、先頭から 4 文字目を起点とした 4 文字からなる文字列 dcba は、一方を並べ替えると他方になるが、先頭から 4 を共通して使用しているため条件を満たさない。他の取り出し方をしても条件をみたすことはない。


入力例3

8 1
issample

出力例3

YES

Submit提出する