AtCoder Regular Contest 024
C
だれじゃ
AtCoder
⌀ 1844
原题
← BD →
翻译中…

Problem Statement

翻译中…

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

翻译中…

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

翻译中…

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

翻译中…

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

翻译中…

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

翻译中…

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

翻译中…

Input

翻译中…

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

翻译中…

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$ 点が与えられる。
翻译中…

Output

翻译中…

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

翻译中…

样例

Input #1
8 3
abcdbcae
Output #1
YES
先頭から $1$ 文字目を起点とした $3$ 文字からなる文字列 $abc$ と、先頭から $5$ 文字目を起点とした $3$ 文字からなる文字列 $bca$ は、一方を並べ替えると他方になるので、長さ $3$ の「アナグラムダジャレ」を含むといえる。
Input #2
7 4
abcdcba
Output #2
NO
先頭から $1$ 文字目を起点とした $4$ 文字からなる文字列 $abcd$ と、先頭から $4$ 文字目を起点とした $4$ 文字からなる文字列 $dcba$ は、一方を並べ替えると他方になるが、先頭から $4$ を共通して使用しているため条件を満たさない。他の取り出し方をしても条件をみたすことはない。
Input #3
8 1
issample
Output #3
YES
题目信息
题号
arc024_3
时间限制
3 s
内存限制
256 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。