시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB43126165.112%

문제

알파벳 소문자로만 이루어진 문자열 S가 주어진다. 사전에는 K개의 단어가 사전 순으로 등재되어 있다. 또한, 사전의 각 단어에는 ‘단어 번호’가 있다. 사전에서 i번째로 등장하는 단어의 번호는 i이다.

우리가 사용할 압축 방법은, 문자열을 사전에 등재된 단어들로 쪼개어, 각 단어를 해당하는 단어 번호로 바꾸는 것이다. 같은 단어를 여러 번 사용해도 된다.

주어진 문자열을 압축했을 때, 결과적으로 나오는 수열의 길이가 가장 짧게 되도록 압축하라.

입력

첫째 줄에 K가 주어진다. (1 ≤ ≤ 104)

둘째 줄부터 K개의 줄에 걸쳐 1번부터 사전 순으로 사전의 단어가 주어진다. 각 단어는 알파벳 소문자로만 이루어져 있고, 길이는 1자 이상 103자 이하이다. 중복된 단어는 주어지지 않는다.

마지막 줄에는 우리가 압축할 문자열 S가 주어진다. S의 길이는 1자 이상 105자 이하이다.

출력

첫째 줄에 압축 결과 수열의 길이를 출력한다.

둘째 줄에 수열을 공백으로 구분하여 출력한다. 답이 여러 개라면, 그중에서 사전 순으로 가장 먼저 오는 것을 출력한다.

만약, 압축이 불가능하다면 첫 줄에 impossible을 출력한다.

예제 입력 1

8
a
abc
b
c
d
def
e
f
abcdef

예제 출력 1

2
2 6

문자열 “abcdef”는 “a” + “b” + “c” + “d” + “e” + “f” 여섯 조각으로 쪼개서 압축할 수도 있고, “abc” + “d” + “e” + “f” 네 조각, 또는 “a” + “b” + “c” + “def” 네 조각으로도 압축할 수 있지만, 사전의 2번째 단어 “abc”와 6번째 단어 “def” 두 조각으로만 쪼개서 압축하는 것이 더 짧다.

예제 입력 2

6
able
conceiv
in
inc
ivable
once
inconceivable

예제 출력 2

3
3 2 1

“inconceivable”은 “in” + “conceiv” + “able” (3 2 1)과 "inc” + “once” + “ivable” (4 6 5) 두 방법으로 압축할 수 있지만, 수열 (3 2 1)이 (4 6 5)보다 사전 순으로 먼저 오기 때문에 (3 2 1)을 출력한다.

예제 입력 3

1
peanutbutter
bojackhorseman

예제 출력 3

impossible

“bojackhorseman”은 사전에 있는 단어를 사용하여 압축될 수 없으므로, "impossible”을 출력한다.

출처

University > 서강대학교 > 2019 Sogang Programming Contest > Champion G번