First!
시간 제한1초메모리 제한128 MB
알파벳 순서를 바꿀 때 입력된 문자열 중 어떤 것이 사전순으로 가장 앞에 올 수 있는지 모두 찾는 문제다.
문제
베시(Bessie)가 문자열을 가지고 놀고 있습니다. 베시는 알파벳의 순서를 바꾸면 어떤 문자열을 사전순(lexicographic order)에서 다른 모든 문자열보다 앞에 오게 만들 수 있다는 것을 발견했습니다.
예를 들어 문자열 omm, moo, mom, ommnom이 있을 때, 표준 알파벳 순서를 사용하면 mom을 맨 앞에 오게 할 수 있고, 알파벳 순서를 abcdefghijklonmpqrstuvwxyz로 바꾸면 omm을 맨 앞에 오게 할 수 있습니다. 하지만 어떤 알파벳 순서로도 moo나 ommnom을 맨 앞에 오게 만들 수는 없습니다.
알파벳 순서를 자유롭게 재배열했을 때 사전순으로 맨 앞에 올 수 있는 문자열이 어떤 것들인지 구하세요.
문자열 가 문자열 보다 사전순으로 앞서는지는 다음과 같이 판단합니다. 두 문자열이 처음으로 달라지는 위치 를 찾습니다. 그런 위치가 없다면, 의 길이가 보다 짧을 때 가 보다 앞섭니다. 그런 위치가 있다면, 알파벳에서 가 보다 먼저 나올 때 가 보다 앞섭니다.
입력
- 첫째 줄: 문자열의 개수 ().
- 둘째 줄부터 번째 줄까지: 각 줄에 비어 있지 않은 문자열이 하나씩 주어집니다. 모든 문자열의 길이 합은 이하입니다. 모든 문자는 소문자
a부터z까지입니다. 서로 같은 문자열은 주어지지 않습니다.
출력
- 첫째 줄: 사전순으로 맨 앞에 올 수 있는 문자열의 개수 .
- 둘째 줄부터 번째 줄까지: 조건을 만족하는 개의 문자열을, 입력에 등장한 순서 그대로 출력합니다.
힌트
표준 알파벳에서는 네 개의 예시 문자열 중 mom이 사전순으로 가장 작으므로 mom이 맨 앞에 올 수 있습니다. o가 n보다 앞서는 알파벳 abcdefghijklonmpqrstuvwxyz를 사용하면 omm이 가장 작아지므로 omm이 맨 앞에 올 수 있습니다. 반면 어떤 알파벳 순서로도 moo와 ommnom은 맨 앞에 올 수 없으므로, 정확히 두 개의 문자열이 조건을 만족합니다.