決まり字 Erlang(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
これは、B ランクの問題としてスキルチェックに出題されていた問題です。試しに解いてみましょう。
現時点では自力で正解することができない場合は、この問題を飛ばして次の問題に進んでください。
この問題の後に続く 5 つの問題に順番に取り組むことで、
この「決まり字」の問題を解くために必要な知識や考えた方を身につけることができます。
B ランク獲得に向けた学習にお役立てください。
百人一首とは、100首の和歌の集まりです。
1首の和歌は、上の句と下の句の1対からなります。
例えば、天智天皇によって詠まれた百人一首の一番目の和歌は次のようなものです。
> 上の句: あきのたの かりほのいほの とまをあらみ
> 下の句: わかころもては つゆにぬれつつ
百人一首を用いたカルタは、読み上げられた上の句に対応する下の句が書かれた札を取る速さを競うゲームです。
このゲームを競技するときには、一刻も早く読まれた和歌に対応する札をとるために、各和歌の **決まり字** を知ることが重要です。
決まり字とは、和歌を一つに特定するために必要な最小の上の句の先頭何文字かの文字列です。
例えば、「あき」から始まる和歌の上の句は次の2つだけです。
* あきのたの かりほのいほの とまをあらみ
* あきかぜに たなびくくもの たへまより
ですので、「あきの」と「あきか」がそれぞれの和歌の決まり字となります。
複数の和歌の上の句が与えられるので、その決まり字を求めるプログラムを作成してください。
- 入力される値
-
n m
s_1
s_2
...
s_n
* 1 行目では、和歌の数 n と決まり字を知りたい和歌の番号 m が与えられます。
* 2 行目から n + 1 行目までの各行では、和歌の上の句が与えられます。i + 1 (1 ≦ i ≦ n) 行目には、和歌 i の上の句が与えられます。
* 入力は合計で n + 1 行となり、入力の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
和歌 m の決まり字を一行で出力してください。
最後は改行し、余計な文字、空行を含んではいけません。
- 条件
-
* 1 ≦ m ≦ n ≦ 100
* 1 ≦ |s_i| ≦ 100
* s_i は英小文字からなる
* s_i ≠ s_j (i ≠ j)
* s_i が s_j (i ≠ j) の接頭辞に完全に含まれることはない
- 入力例1
-
2 1
akinotanokarihonoionotomaoarami
akikazenitanabikukumonotaemayori
- 出力例1
-
akin
- 入力例2
-
9 3
kirigirisunakuyashimoyonosamushironi
kimigatameharunononiidetewakanatsumu
chihayaburukamiyomokikazutatsutagawa
ookotonotaeteshinakuwanakanakani
ooeyamaikunonomichinotokereba
ookenakuukiyonotaminioukana
chigiriokishisasemogatsuyuoinochinite
kimigatameoshikarazarishiinochisae
chigirikinakataminisodeoshiboritsusu
- 出力例2
-
chih
- 入力例3
-
7 2
murasamenotsuyumomadahinumakinohani
suminoenokishiniyorunamiyorusaeya
meguriaitemishiyasoretomowakanumani
fukukaraniakinokusakinoshiorureba
sabishisaniyadootachiidetenagamureba
hototogisunakitsurukataonagamureba
seohayamiiwanisekarurutakigawano
- 出力例3
-
su
- 入力例4
-
6 3
aaaaaa
ababab
aaab
bbbc
c
abc
- 出力例4
-
aaab
