Manber-Myers 알고리즘 썸네일형 리스트형 Suffix Array & LCP Array(Longest Common Prefix Array) Suffix Array는 번역하면 접미사 배열으로 다양한 문자열 문제들을 해결할 수 있는 매우 강력한 자료구조 입니다. Suffix Array는 문자열의 Suffix를 사전순으로 정렬한 배열입니다. 예를 들어 banana라는 문자가 있다면 Suffix Array는 다음과 같이 됩니다. 하지만 Suffix Array를 이렇게 문자열로 가지고 있을 경우 O(N^2)의 공간 복잡도를 가지게 될 것입니다. 그렇기 때문에 Suffix Array는 몇번째 접미사인지 나타내는 정수 i만 가지는 정수형 자료 구조형태를 가집니다. 다음과 같이 말이죠. 자 이제 Suffix Array의 정의에 대해 알았으니 구현을 해 볼 차례입니다. 단순하게 접미사 배열을 구한다면 접미사를 구한다음 정렬을 하는 방법이 있겠군요 하지만 이.. 더보기 이전 1 다음
