Segane väljund

시간 제한3초메모리 제한1024 MB

요약

하나의 미지 문자열을 복사한 N개를 동시에 실행해 뒤섞인 결과 S가 주어질 때, S를 만들 수 있는 모든 문자열을 중복 없이 찾아 사전순으로 출력한다. 각 문자열은 N개의 복사본을 인터리빙해 S가 되어야 한다. 서로 다른 인터리빙이 같은 문자열을 만들 수 있으므로 답은 문자열 단위로 중복을 제거하며, 탐색 공간을 줄이기 위해 각 복사본의 진행 위치를 상태로 두고 백트래킹한다. N^L이 2·10^7 이하라는 보장이 완전 탐색을 가능하게 한다. 검색 중 각 단계에서 N개 복사본이 같은 문자를 내놓을 때 가지를 합쳐 중복을 피하는 가지치기가 필요하다. 출력은 가능한 문자열의 개수와 사전순 정렬된 목록이다. 주어진 S를 정확히 N개의 동일 문자열 인터리빙으로 분해하는 문제다. T개의 부분 테스트가 주어지며 각 테스트마다 결과를 출력한다. 입력 문자열은 소문자만 포함한다. 이 문제는 인터뷰보다 대회용에 가깝다. 상태 공간이 크고 중복 제거와 가지치기 설계가 핵심이기 때문이다. 브루트포스 백트래킹에 문자열 비교를 결합한다. 완전 탐색이 가능하도록 제약이 설계되어 있다. 따라서 레이팅은 8이다. 주제는 백트래킹, 문자열, 조합론, 구현이다. 면접 문제로는 부적합하다. 대

난이도: 어려움10점 중 8점
유형: 백트래킹, 문자열, 조합론, 구현
정답자: 아직 제출이 없습니다

문제

Juku katsetas erinevaid käsureaprogramme. Enamiku programmide mitmekordsel järjest käivitamisel sai ta mitu korda sama väljundi. Näiteks programm pwd väljastas kahekordsel järjest käivitamisel järgneva:

/home/juku/lahendused/segane
/home/juku/lahendused/segane

Samas on selline väljund garanteeritud vaid siis, kui programme jooksutatakse üksteise järel. Kui Juku käivitas ühe programmi mitu eksemplari korraga, märkas ta, et nende väljundid põimusid, andes igal katsel erineva tulemuse. Näiteks pwd kaht eksemplari korraga jooksutades sai Juku kahel katsel järgnevad väljundid:

/home//homjukue/ju/lahkeundu/sedl/ahseeganen
dused/segane

/h/ohomme/e/juku/lajukhue/landusehedn/segadunseed/
segane

Seejuures märkas Juku, et kuigi programmi erinevate eksemplaride väljastatud märgid võivad olla üksteise vahel, väljastati programmi iga eksemplari kogu väljund täielikult ja kõik ühe eksemplari väljastatud märgid omavahel õiges järjekorras.

Juku otsustas seda veidrat nähtust korduvalt katsetada, kuid peale pisut aega proovimist märkas ta, et ta ei tea tegelikult mõnede programmide väljundit. Nüüd tahab ta olemasoleva info põhjal võimalikud väljundid taastada.

입력

Selles ülesandes võib sisend koosneda mitmest alamtestist. Sisendi esimesel real on alamtestide arv $T$ ( $1 \le T \le 20$ ).

Iga alamtest koosneb kahest reast. Esimesel real on käivitatud programmide arv $N$ ( $2 \le N \le 10$ ). Teisel real on sõne $S$ , ühe programmi $N$ eksemplari samaaegsel käivitamisel saadud väljund. Lihtsuse huvides koosneb see sõne vaid ladina tähestiku väiketähtedest ning ei sisalda tühikuid, reavahetusi ega muid erimärke.

출력

Iga alamtesti kohta väljastada kaks rida. Esimesele reale väljastada täisarv, mis näitab programmi kõigi võimalike väljundite arvu. Teisele reale väljastada programmi kõik võimalikud väljundid tühikutega eraldatult ja tähestikulises järjekorras.

Olgu $L$ programmi ühe eksemplari väljundi pikkus ( $S$ pikkus on siis $N \cdot L$ ). Iga alamtesti puhul on garanteeritud, et $N^L \le 2 \cdot 10^7$ . Järgnev tabel näitab võimalikele $N$ väärtustele vastavaid maksimaalseid $L$ väärtusi:

$N$	$\max{L}$
$2$	$24$
$3$	$15$
$4$	$12$
$5$	$10$
$6$	$9$
$7$	$8$
$8$	$8$
$9$	$7$
$10$	$7$

Esimeses alamtestis on programmi eksemplaride väljundid väljastatud järjest. Teises alamtestis võisid programmi eksemplarid väljastada märke paljudel erinevatel viisidel põimitult, kuid programmi väljundi jaoks on vaid üks võimalik variant. Kolmandas alamtestis on toodud olukord, kus programm võis väljastada ühe kahest võimalikust väljundist.

예제1

예제 1

입력

4
2
abcdabcd
5
aaaaaaaaaa
2
aabbaabb
4
eerrrroereorrrorrror

예상 출력

1
abcd
1
aa
2
aabb abab
1
error