알고리즘/문자열
2021. 2. 16.
Suffix Array와 LCP배열
문자열 \(S\)가 주어졌을 때, 이 문자열의 모든 접미사(suffix)를 사전순으로 정렬해 봅시다. 가장 단순한 방법은 \(|S|\)개의 suffix를 만든다음, 직접 정렬하는 것입니다. 이 방법을 이용하면 \(O(n^2 \log n)\)의 시간복잡도로 Suffix Array를 만들 수 있습니다. (\(n = |S|\)) www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 물론 이는 문자열의 길이가 조금만 길어져도 쓸 수 없는 방법이므로, 다른 방법을 생각해 봅시다. 다음과 같은 문자열이 있습니다. (0-index) \(S = \) "ab..
