아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

First!

시간 제한1초메모리 제한128 MB

요약
알파벳 순서를 바꿀 때 입력된 문자열 중 어떤 것이 사전순으로 가장 앞에 올 수 있는지 모두 찾는 문제다.
난이도

어려움10점 중 8점

유형
문자열, 트라이, 그래프, 위상 정렬
정답자
아직 제출이 없습니다

문제

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

예를 들어 문자열 omm, moo, mom, ommnom이 있을 때, 표준 알파벳 순서를 사용하면 mom을 맨 앞에 오게 할 수 있고, 알파벳 순서를 abcdefghijklonmpqrstuvwxyz로 바꾸면 omm을 맨 앞에 오게 할 수 있습니다. 하지만 어떤 알파벳 순서로도 moo나 ommnom을 맨 앞에 오게 만들 수는 없습니다.

알파벳 순서를 자유롭게 재배열했을 때 사전순으로 맨 앞에 올 수 있는 문자열이 어떤 것들인지 구하세요.

문자열 XX가 문자열 YY보다 사전순으로 앞서는지는 다음과 같이 판단합니다. 두 문자열이 처음으로 달라지는 위치 jj를 찾습니다. 그런 위치가 없다면, XX의 길이가 YY보다 짧을 때 XX가 YY보다 앞섭니다. 그런 위치가 있다면, 알파벳에서 X[j]X[j]가 Y[j]Y[j]보다 먼저 나올 때 XX가 YY보다 앞섭니다.

입력

  • 첫째 줄: 문자열의 개수 NN (1≤N≤300001 \le N \le 30000).
  • 둘째 줄부터 N+1N+1번째 줄까지: 각 줄에 비어 있지 않은 문자열이 하나씩 주어집니다. 모든 문자열의 길이 합은 300000300000 이하입니다. 모든 문자는 소문자 a부터 z까지입니다. 서로 같은 문자열은 주어지지 않습니다.

출력

  • 첫째 줄: 사전순으로 맨 앞에 올 수 있는 문자열의 개수 KK.
  • 둘째 줄부터 K+1K+1번째 줄까지: 조건을 만족하는 KK개의 문자열을, 입력에 등장한 순서 그대로 출력합니다.

힌트

표준 알파벳에서는 네 개의 예시 문자열 중 mom이 사전순으로 가장 작으므로 mom이 맨 앞에 올 수 있습니다. o가 n보다 앞서는 알파벳 abcdefghijklonmpqrstuvwxyz를 사용하면 omm이 가장 작아지므로 omm이 맨 앞에 올 수 있습니다. 반면 어떤 알파벳 순서로도 moo와 ommnom은 맨 앞에 올 수 없으므로, 정확히 두 개의 문자열이 조건을 만족합니다.

예제3

  1. 예제 1

    입력
    4
    omm
    moo
    mom
    ommnom
    
    예상 출력
    2
    omm
    mom
    
  2. 예제 2

    입력
    1
    a
    
    예상 출력
    1
    a
    
  3. 예제 3

    입력
    3
    a
    b
    c
    
    예상 출력
    3
    a
    b
    c