문자열 압축
시간 제한2초메모리 제한1024 MB
K개 단어로 이루어진 사전이 주어질 때, 문자열 S를 사전 단어들로 쪼개어 만들어지는 단어 번호 수열의 길이가 최소가 되도록 하고, 그중 사전 순으로 가장 앞서는 수열을 출력한다.
문제
알파벳 소문자로만 이루어진 문자열 S가 주어진다. 사전에는 K개의 단어가 사전 순으로 등재되어 있다. 또한, 사전의 각 단어에는 ‘단어 번호’가 있다. 사전에서 i번째로 등장하는 단어의 번호는 i이다.
우리가 사용할 압축 방법은, 문자열을 사전에 등재된 단어들로 쪼개어, 각 단어를 해당하는 단어 번호로 바꾸는 것이다. 같은 단어를 여러 번 사용해도 된다.
주어진 문자열을 압축했을 때, 결과적으로 나오는 수열의 길이가 가장 짧게 되도록 압축하라.
입력
첫째 줄에 K가 주어진다. (1 ≤ K ≤ 104)
둘째 줄부터 K개의 줄에 걸쳐 1번부터 사전 순으로 사전의 단어가 주어진다. 각 단어는 알파벳 소문자로만 이루어져 있고, 길이는 1자 이상 103자 이하이다. 중복된 단어는 주어지지 않는다.
마지막 줄에는 우리가 압축할 문자열 S가 주어진다. S의 길이는 1자 이상 105자 이하이다.
출력
첫째 줄에 압축 결과 수열의 길이를 출력한다.
둘째 줄에 수열을 공백으로 구분하여 출력한다. 답이 여러 개라면, 그중에서 사전 순으로 가장 먼저 오는 것을 출력한다.
만약, 압축이 불가능하다면 첫 줄에 impossible을 출력한다.