-
문자열로 나오는 문제들은 접미사 배열을 이용해 어려운 문제들도 간단히 해결이 가능하다.
접미사 배열은 말 그대로 어떤 문자들의 접미사들을 모아놓은 묶음이다.
예를 들면
Algorithm이면 접미사들로는
m, hm, thm, ithm, rithm, orithm, gorithm, lgorithm, Algorithm,이 있을 건데
이것들을 사전 순데로 정리해서
Algorithm
gorithm
hm
ithm
m
orithm
rithm
으로 나타낸 것이다.
어떤 점에서 유용하냐 그냥 정렬만 해두었으면서 라 할수도 있다
하지만 이게 사전순으로 정리되어 있다는 점을 주목할 필요가 있다.
우리가 어떤 문자열을 찾는다면
처음부터 모두 뒤져보는 원시적인 방법을 써야하지만 O(N*N)
위 처럼 정리해두면 O(N*logN)이 걸린다.
단순하면서도 나중에 써먹을 곳이 많은 자료구조이다.