자료구조 - 접미사 배열(Suffix array, 맨버-마이어스 알고리즘)
1. 접미사 배열 접미사 배열은 문자열 형태의 데이터가 갖는 모든 접미사를 사전 순 정렬한 것을 의미한다. 접미사 배열은 문자열 검색, 전문 검색 등에 활용하기 위해서 많이 쓰인다. 접미사 배열로 검색하면 아래와 같은 예시를 가장 많이 볼 수 있다. 이를 통해 간단히 이해해보자. 기존 배열(original array) 접미사 배열(suffix array) banana a anana ana nana anana ana banana na na a nana 이해하기 어렵지 않다. banana 라는 문자열의 모든 접미사는 자기 자신을 포함해, 뒤에서 부터 한 글자씩 잘라낸 부분이라고 보면 된다. 위의 표를 보면 좌측의 기존 접미사를 저장한 배열이 정렬 후 우측과 같이 정렬 상태가 됨을 알 수 있다. 이제 보니, ..
