cho.sh

오래된 기억

아직 제출이 없습니다시간 제한10초메모리 제한128 MB

문제

서기 4272년, 세 차례의 세계 컴퓨터 바이러스 전쟁을 기적적으로 살아남아 올해 90세가 된 프로그래밍 문학의 대가 아이작 코넬 팬서캐롤 박사가 노벨 문학상을 받았다. 언론은 그의 삶을 낱낱이 보도했지만, 단 하나 보도하지 못한 것이 있었다. 바로 그가 초등학생이던 시절에 쓴 수필이다. 박사는 그 수필의 사본을 가지고 있었고 기꺼이 공개하려 했지만, 문제는 그 사본이 제3차 세계 컴퓨터 바이러스 전쟁 동안 여러 번 컴퓨터 바이러스에 감염되어 본문이 훼손되었을 수 있다는 점이었다.

조사 결과 사본이 실제로 훼손되었음이 밝혀졌다. 어떻게 알 수 있었을까? 80여 년 전, 그의 동창들이 감염 이전의 원본 수필을 자신의 뇌에 옮겨 두었기 때문이다. 솔리드 스테이트 브레인의 등장으로, 한 번 뇌에 옮긴 글은 이제 수백 년이 지나도 완벽하게 보존된다. 용량 한계 때문에 글 전체를 기억하는 사람은 없었지만, 우리는 한 동창의 뇌에서 글의 일부를 복원해 낼 수 있었다. 안타깝게도 그 일부는 현재 남아 있는 사본과 완전히 일치하지 않았다. 바이러스 감염이 없었다면 일어나지 않았을 일이다.

지금까지 밝혀진 바이러스의 동작은 다음과 같다. 바이러스는 수필을 감염시킬 때마다 아래 세 가지 중 하나를 수행한다.

  1. 본문의 임의의 위치에 임의의 문자 하나를 삽입한다. (예: "ABCD" → "ABCZD")
  2. 본문에서 임의의 문자 하나를 골라 다른 문자로 바꾼다. (예: "ABCD" → "ABXD")
  3. 본문에서 임의의 문자 하나를 골라 삭제한다. (예: "ABCD" → "ACD")

또한 침입 기록의 양으로부터 바이러스가 사본을 감염시킨 최대 횟수를 알아낼 수 있다. 다행히 대부분의 동창은 원본 수필의 일부(이하 조각이라 부른다)를 적어도 하나씩 기억하고 있었다. 모든 증거를 종합하면 원본 수필을 복원할 수 있을지도 모른다. 기자이자 컴퓨터 과학자인 당신은, 주어진 조각들과 손에 있는 훼손된 사본에 부합하는 원본 후보(들)를 계산하는 프로그램을 작성하여 원본 수필을 복원하려 한다.

입력

입력은 여러 개의 데이터셋으로 이루어진다. 데이터셋의 수는 100개를 넘지 않는다. 각 데이터셋의 형식은 다음과 같다.

  • 첫 줄: 두 정수 $d$와 $n$ ($1 \le d \le 2$, $1 \le n \le 30$). $d$는 바이러스가 사본을 감염시킨 최대 횟수, $n$은 조각의 개수이다.
  • 둘째 줄: 손에 있는 훼손된 사본의 본문(이하 훼손된 본문). 길이는 40자 이하이다.
  • 이어지는 $n$개의 줄: 각 줄은 한 동창이 기억하는 원본 수필의 일부인 조각이다. 각 조각의 길이는 13자 이상 20자 이하이며, 모든 조각의 길이는 서로 같다.

훼손된 본문과 조각에 쓰이는 문자는 대문자 알파벳('A'–'Z')과 마침표('.')뿐이다. 그가 사용한 언어는 단어 사이에 공백을 두지 않으므로 본문에 공백은 나타나지 않는다.

0 0만 있는 줄이 나오면 입력이 끝난다.

동창이 매우 많았으므로, 원본 수필에 등장하는 모든 문자는 적어도 하나의 조각으로 덮인다고 가정할 수 있다. 한 조각이 원본 수필을 여러 번 덮을 수도 있고, 원본 수필에는 반복이 있을 수도 있다. 한편 일부 동창이 관련 없는 조각을 잘못 제공했을 수 있으므로, 어떤 조각은 원본 수필에 전혀 나타나지 않을 수도 있다.

출력

각 데이터셋에 대해 다음을 출력한다.

원본 수필의 후보 개수를 $c$라 하자. 문자열 $S$가 후보가 되려면 아래 두 조건을 모두 만족해야 한다.

  • $S$에 감염(삽입·치환·삭제)을 최대 $d$번 적용하여 훼손된 본문을 만들 수 있다. 다시 말해 $S$와 훼손된 본문 사이의 편집 거리가 $d$ 이하이다.
  • $S$의 모든 위치가 적어도 하나의 조각으로 덮인다. 어떤 위치가 조각으로 덮인다는 것은, 그 위치를 포함하도록 어떤 조각이 $S$의 연속 부분 문자열로 나타난다는 뜻이다.

먼저 $c$를 한 줄에 출력한다. $c$가 5 이하이면, 이어서 후보들을 사전순으로 한 줄에 하나씩 총 $c$줄에 걸쳐 출력한다. 사전순에서 마침표('.')는 다른 모든 문자보다 앞선다. $c$는 항상 1 이상임이 보장된다. 출력에는 위에서 언급한 문자 외의 어떤 문자도 포함해서는 안 된다.