5052 - 전화번호 목록

주어지는 전화번호들을 사전순으로 정렬하고 어떤 문자열이 바로 다음 문자열의 접두어라면 고민없이 "NO" 를 출력하고 다음 테스트케이스로 넘어가면 된다.

다음 다음, 혹은 그 이전이나 이후와는 비교할 필요가 없는 게, 이전은 이미 비교가 끝났을 것이고, 다음 이후에 존재한다는 것은 바로 다음도 접두어라는 의미이기 때문이다.

1701 - 소녀시대 공식팬클럽 회장

2번 이상 나타나는 부분문자열을 찾고 그 최대 길이를 출력하는 문제이다.

Suffix Array 를 사용했는데,
길이가 n인 문자열 s에 대해 s[i...n]의 suffix (n개)를 나열한다. 예를들어, abbac 라면

abbac
bbac
bac
ac
c

와 같이 나오는데, 이걸 사전순으로 정렬하여 다음과 같이 만든다.

abbac
ac
bac
bbac
c

위 suffix array에 대해 서로 문자열을 비교한다.
i번 문자열과 i+1번 문자열에 대해 [0...j]를 비교. [i][j] 와 [i+1][j] 가 다를 때까지의 길이가 부분문자열의 길이가 된다.
이는 "모든 부분문자열은 모든 접미사의 접두사들"이기 때문이다.

Suffix Array는 간단한 구현으로 많은 문제에 영감을 줄 수 있지만, 위와 같이 N개에 대해 저장하거나 N²의 시간복잡도를 가지는 경우가 있어서 길이가 1만 정도만 넘어도 사용하기 힘들어진다고 한다.

길이가 10만을 넘는 문자열에 대해서 부분문자열은 어떻게 찾는지 고심해봐야겠다.