ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 접미사배열
    알고리즘/자료구조 2015. 2. 24. 21:23

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

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

    예를 들면 


    Algorithm이면 접미사들로는

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

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


    Algorithm

    gorithm

    hm

    ithm

    m

    orithm

    rithm

    으로 나타낸 것이다.


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


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

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

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


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


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


    '알고리즘 > 자료구조' 카테고리의 다른 글

    오일러회로  (0) 2015.02.27
    트라이  (0) 2015.02.27
    트립(Treap)  (0) 2015.02.25
    접미사배열  (0) 2015.02.24
    KMP 알고리즘  (0) 2015.02.24
    BIT(Binary Indexed Tree)  (0) 2015.02.21

    댓글 0

Designed by Tistory.