접미사배열

문자열로 나오는 문제들은 접미사 배열을 이용해 어려운 문제들도 간단히 해결이 가능하다.

접미사 배열은 말 그대로 어떤 문자들의 접미사들을 모아놓은 묶음이다.

예를 들면 

Algorithm이면 접미사들로는

m, hm, thm, ithm, rithm, orithm, gorithm, lgorithm, Algorithm,이 있을 건데

이것들을 사전 순데로 정리해서

Algorithm

gorithm

hm

ithm

m

orithm

rithm

으로 나타낸 것이다.

어떤 점에서 유용하냐 그냥 정렬만 해두었으면서 라 할수도 있다

하지만 이게 사전순으로 정리되어 있다는 점을 주목할 필요가 있다.

우리가 어떤 문자열을 찾는다면

처음부터 모두 뒤져보는 원시적인 방법을 써야하지만 O(N*N)

위 처럼 정리해두면 O(N*logN)이 걸린다.

단순하면서도 나중에 써먹을 곳이 많은 자료구조이다.