SCPC 2018 본선 2번 풀이. 외계메시지

문제 설명(요약)

N개의 정수가 순서대로 주어진다. 이 수열에서 X번 이상 반복되는 패턴 중 가장 긴 패턴의 길이를 구하여라. 단, 패턴은 부분적으로 서로 겹칠 수 있다.

제약 조건: N <= 50,000.

실행 조건: 테스트 케이스 50개에 대한 실행시간 총합 0.5초 이내, 메모리 총합 256MB 이내

부분문제 1 풀이

패턴으로 가능한 가짓수는 O(N²)개이므로, 각 패턴이 있을 수 있는 O(N)개의 위치에 대해 실제로 있는지를 비교해 확인하는 것이 위치마다 O(N)이 소요되므로 전체 시간은 O(N⁴).

따라서 N <= 50인 부분문제 1은 해결된다. (구현은 안 해 보았다)

부분문제 2 풀이

조금만 생각해보면, 시작 위치가 같은 패턴들은 한 번에 비교하면 O(N) 내에 모두 계산 가능함을 알 수 있다. 따라서 DP[i][j][k] = (i와 j에서 시작하는 길이가 k인 두 패턴의 일치 여부)라고 하면 DP[i][j][k] = DP[i][j][k-1] && (S[i+k-1] == S[j+k-1])이다. 이 표를 이용해 각 패턴이 다른 패턴과 일치하는지 여부를 확인하면 전체 시간은 O(N³).

따라서 N <= 500인 부분문제 2는 해결될 것이다. (구현은 안 해 보았다. 0.5초로 시간이 촉박하므로, 확실치는 않다)

부분문제 3 풀이

Suffix Array를 활용한다. 0부터 N-1까지 배열에 넣고, std::sort를 사용해 정렬한다. 이때 정렬 기준은 부분문자열의 사전순서를 활용한다. Suffix Array를 구했으면, 길이 X인 Window를 Suffix Array 위에서 움직이면서 해당 구간의 양 끝 문자열끼리 비교하여 해당 Window 내의 최대 패턴 매치 길이를 기록한다. 이 길이 중 최댓값을 구하면 원하는 답이 된다. 전체 소요시간은 O(N² lg N).

따라서 N <= 5,000인 부분문제 3은 해결된다.

부분문제 4 풀이

부분문제 3의 구현을 최적화한다.

(1) Suffix Array를 계산할 때 잘 알려진 Sparse Trick을 써서 루프를 ceil(lg N)회만 돌도록 할 수 있다. 시간복잡도는 O(N lg N lg N). 하지만 이것으로는 충분치 않으므로 std::sort 대신 Radix Sort를 손수 구현해 O(N lg N)으로 줄여야 한다.

(2) 길이 X인 Window에 대해 계산할 때는 Sparse Trick이 남긴 Sparse Table을 이용해 이진탐색을 한다. 그러면 하나의 Window에서의 소요시간을 O(lg N)으로 줄일 수 있다.

이렇게 전부 줄여 O(N lg N)을 만들어야만 N <= 50,000이면서 제한시간 0.5초 이내라는 악랄한 조건을 통과할 수 있다.