접미사 배열
문자열의 모든 접미사(뒤쪽 끝부분, 예를 들어 banana의 a · na · ana …)를 사전 순으로 정렬하고, 각 접미사가 시작하는 위치만 배열에 담은 것이다. 모든 부분 문자열은 어떤 접미사의 앞부분이므로, 이 정렬된 배열에서 이진 탐색으로 「이 부분 문자열이 있나」 같은 질문에 빠르게 답할 수 있다. 같은 부분 문자열로 시작하는 접미사들은 정렬된 배열에서 한 덩어리로 붙어 있으므로, 그 덩어리의 시작과 끝을 이진 탐색으로 찾으면 덩어리 크기가 곧 그 부분 문자열이 나오는 횟수다.
자신만의 철학을 만들어가는 중입니다.
최상단으로 이동했습니다!