No.3626 Not a Prefix
問題文最終更新日: 2026-08-17 21:46:40
yukicoder contest 509の他の問題:
問題文
英小文字からなる空でない文字列が $N$ 個与えられます。$i ~ (1 \leq i \leq N)$ 番目の文字列は $S_i$ です。
あなたはこれらの文字列から $M$ 個自由に選ぶことができます。選んだ文字列はそれぞれ $T_1, T_2. \cdots, T_M$ とします。
以下の条件をすべて満たす文字列 $X$ が存在するような選び方が存在するか判定してください。そのような選び方存在する場合は、$X$ としてあり得る辞書順最小の文字列を出力してください。
- $X$ は英小文字からなる空でない文字列である。
- 任意の $k ~ (1 \leq k \leq M)$ について、 $X$ は $T_k$ の接頭辞でない。
- 任意の $k ~ (1 \leq k \leq M)$ について、 $T_k$ は $X$ の接頭辞でない。
制約
- $N, M$ は整数
- $1 \leq M \leq N \leq 2 \times 10^5$
- $S_i$ は英小文字からなる空でない文字列
- $S_1, S_2, \cdots, S_N$ の長さの総和は $5 \times 10^5$ 以下
入力
各テストケースは以下の形式で与えられる。
$N$ $M$ $S_1$ $S_2$ $\vdots$ $S_N$
出力
条件を満たす選び方が存在するならば Yes 、そうでないならば No を出力せよ。
存在する場合、改行した後 $X$ としてあり得る辞書順最小の文字列を出力せよ。
サンプル
サンプル1
入力
5 2 apple apricot banana cat dog
出力
Yes a
例えば $T_1, T_2$ として banana, cat を選ぶことで、$X =$ a が条件を満たします。
サンプル2
入力
26 26 a b c d e f g h i j k l m n o p q r s t u v w x y z
出力
No
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
ぽえ