1등!

베시(Bessie)는 또 문자열을 가지고 놀고 있었다. 베시는 알파벳의 순서를 바꾸면 어떤 문자열들을 사전순(사전식 순서)으로 다른 모든 문자열보다 앞서게 만들 수 있다는 것을 발견했다.

예를 들어 베시는 문자열 "omm", "moo", "mom", "ommnom"에 대해, 표준 알파벳을 사용하면 "mom"을 가장 앞서게 만들 수 있고, 알파벳 "abcdefghijklonmpqrstuvwxyz"를 사용하면 "omm"을 가장 앞서게 만들 수 있다는 것을 알아냈다. 하지만 베시는 "moo"나 "ommnom"을 가장 앞서게 만드는 방법은 찾아내지 못했다.

알파벳의 순서를 재배열하여 입력의 문자열들 중 어떤 것들이 사전순으로 가장 앞설 수 있는지 계산하여 베시를 도와주자. 문자열 X가 문자열 Y보다 사전순으로 앞서는지 계산하려면, 두 문자열이 처음으로 달라지는 문자의 인덱스 j를 찾는다. 그런 인덱스가 존재하지 않으면, X가 Y보다 짧을 때 X는 Y보다 사전순으로 앞선다. 그렇지 않으면, X[j]가 알파벳에서 Y[j]보다 먼저 나올 때 X는 Y보다 사전순으로 앞선다.

첫째 줄: 베시가 가지고 노는 문자열의 수 N (1 <= N <= 30,000)이 주어진다.

둘째 줄부터 1+N번째 줄까지: 각 줄에 비어 있지 않은 문자열이 주어진다. 모든 문자열의 문자 수의 합은 300,000을 넘지 않는다. 입력의 모든 문자는 소문자 'a'부터 'z'까지이다. 입력에 중복된 문자열은 없다.

첫째 줄: 사전순으로 가장 앞설 수 있는 문자열의 수 K.

둘째 줄부터 1+K번째 줄까지: (1+i)번째 줄에는 사전순으로 가장 앞설 수 있는 i번째 문자열을 출력한다. 문자열들은 입력에 주어진 순서대로 출력해야 한다.

riseoj 작성

출처 올림피아드 > USACO > 2012-2013 > December > Gold