最長共通接尾辞 (Longest Common Suffix) クエリ
(ラップバトル)
n 個の異なる単語リスト と、q 個のクエリ単語 が与えられています。ここでの課題は、各クエリ単語 w に対して、リスト a の中から「w と異なる単語のうち、w との共通する末尾部分が最も長く、かつ辞書順で最小の単語」を見つけることです。入力
入力の最初の行には、文字列の数を表す整数
n (2 ≤ n ≤ 25 000) が与えられます。続く
n 行には、単語が与えられます。各単語は小文字の英字からなり、その長さは最大 30 文字です。次の行には、クエリ単語の数を表す整数
q (1 ≤ q ≤ 25000) が与えられます。続く
q 行には、クエリ単語が与えられます。クエリ単語も小文字の英字からなり、その長さは最大 30 文字です。
出力
各クエリについて、クエリ単語と異なり、共通接尾辞が最も長く、かつ辞書順で最小となるリスト内の単語を 1 行に 1 つ出力してください。
例
Input | Output |
4
perfect
rhyme
crime
time
2
crime
rhyme | time
crime |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB