테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 접미사 배열 (Suffix Array) ======
  * 참고
    * https://en.wikipedia.org/wiki/Suffix_array
    * https://koosaga.com/125
    * https://cp-algorithms.com/string/suffix-array.html
  * 주어진 한개의 문자열에서 어떤 정보를 뽑아내야 할 때 사용할수 있는 가장 강력한 알고리즘이다
  * prefix에 관한 정보는 [[ps:KMP 알고리즘]]이나 [[ps:Z 알고리즘]]으로 대충 해결되는 경우가 많지만, 일반적인 부분문자열에 관한 것은 접미사 배열이 필요한 경우가 많다.
  * 어떤 부분 문자열은 어떤 접미사의 접두사이기 때문에, 모든 접미사를 효율적으로 잘 관리해서 접두사에 대한 정보를 잘 뽑을수 있게 하면, 부분 문자열에 대한 정보를 잘 처리할수 있다
  * 모든 접미사를 뽑았을다고 치면, 사실 이렇게 여러개의 문자열을 처리할수 있는 가장 강력한 도구는 [[ps:트라이]]이다. 하지만, 진짜로 모든 접미사로 트라이를 만들면, 메모리가 O(n^2)이 되어서 터진다.
  * 이것을 좀더 개선해서 효율적으로 O(n)에 자료를 저장하게 만든 suffix tree 라는 구조가 있다고 한다. 그리고 어떻게어떻게 해서 이것을 O(n) 시간에 구축하는 알고리즘도 있다고 한다.
  * 하지만.. 이것보다 더 간단한 구조인, 접미사 배열과 lcp 배열을 사용해서 문제를 풀수도 있다.
    * 접미사 배열은 각 접미사들이 정렬되었을때 몇번째에 오는지 하는 랭크들만 저장해놓은 구조이다. lcp배열은 접미사 배열에서 인접한 접미사들끼리의 LCP를 저장해놓은 구조이다.
    * 따라서 접미사 배열과 lcp 배열은 전부 길이 n까지 정수 배열에 불과하다. 공간복잡도가 suffx tree와 똑같은 O(n)이지만 상수가 훨씬 작다. 
    * 접미사 배열과 lcp 배열을 구축하는 것은 일반적으로는 O(nlogn)의 시간복잡도가 걸리지만, suffix tree에 비하면 알고리즘이 훨씬 간단하다.
      * 실제로는 O(n)에 구축하는 알고리즘이 많이 있다.
  * 접미사 배열과 lcp 배열만 있으면 suffix tree로 할수 있는 태스크를 거의 다 (전부라고 어디서 봤던거 같기도 한데 가물가물..) 할수 있다고 한다.
    * 예를 들면 어떤 두 부분문자열의 LCP를 찾는 쿼리를 해결하는 문제..는 suffix tree에서의 LCA 쿼리를 처리하는 것으로 쿼리당 O(1)이 걸리는데, 접미사배열과 LCP배열이 있다면, LCP배열에서 RMQ쿼리를 처리하는 문제가 되어서 역시 쿼리당 O(1)이 걸린다.
    * 두번 이상 등장하는 가장 긴 부분문자열은 suffix tree에서 depth가 가장 큰 non-leaf 노드를 찾는 방식으로 풀수 있다. 접미사 배열에서는 LCP 배열의 최댓값을 찾는 것으로 풀수있다.

  * 사실 suffix tree에서 dfs를 하면 접미사 배열을 O(n)에 구할수 있다. 또 접미사 배열을 suffix tree로 O(n)에 변환하는 알고리즘도 있다

===== 알고리즘 =====

==== 접미사 배열 ====
  * 위키피디에아 따르면, O(n)에 구축하는 알고리즘이 다양하게 있다고 한다.
    * Prefix doubling, Recursive algorithms, Induced copying algorithms 이렇게 크게 세가지 분류가 있다고 한다
    * 심지어는 2016년에는 in-place로 만드는 알고리즘도 나왔다고 한다
  * 하지만, 인터넷에서 이런 O(n)알고리즘에 대한 강의 자료를 찾기는 쉽지 않다. 한국어로 된 자료는 전혀 찾을수 없었다.
  * 보통 널리 알려진 알고리즘은 O(nlog^2n)의 Manber-Myers 알고리즘이다. 카운팅소트로 바꾸면 O(nlogn)까지 시간복잡도를 줄일수 있다. 

=== Manber-Myers 알고리즘 ===  
  * 참고자료: [[https://plzrun.tistory.com/entry/Suffix-Array-ONlogNlgN%EA%B3%BC-ONlogN-%EA%B5%AC%ED%98%84-%EB%B0%8F-%EC%84%A4%EB%AA%85|plzrun]]
  * 맨버-마이어스 알고리즘이란 이름이 그렇게 유명하지는 않다. 그냥 서픽스 어레이 알고리즘이라고 퉁치고 설명하는 곳들도 많다.
  * 정렬에 일반 O(nlogn) 정렬 알고리즘을 사용하면 전체 시간 복잡도가 O(nlog^2n)이 된다. O(n)짜리 카운팅 소트로 대체하면 O(nlogn)이 된다.
  * O(nlog^2n) 코드는 간단하다. 내가 작성한 것은 대충 이런식.
    * <dkpr py>
def suffix_array(s):
    n = len(s)
    sa = list(range(n))
    g = [ord(x) for x in s] + [0] * n
    d = 1
    while True:
        sa.sort(key=lambda i: (g[i], g[i + d]))
        t = [0] * (n + n)
        t[sa[0]] = 1
        for prev, cur in itertools.pairwise(sa):
            t[cur] = t[prev] + (g[cur] > g[prev] or g[cur + d] > g[prev + d])
        if t[sa[-1]] == n:
            break
        g = t
        d *= 2
    return sa
</dkpr>
      * 비교할때 배열 범위가 넘어가는 것을 처리하는 것이 귀찮아서, 그냥 배열 크기를 2배로 늘려 잡았다.
      * 루프를 d가 len(s)보다 커질때까지 돌리지 않아도, 모든 접미사가 다른 번호를 갖게 되었는지를 t[sa[-1]] == n으로 체크해서 종료시킬수 있다.
  * O(nlogn) 코드는 작성 안해봤다. 아래 말할 SAIS코드를 쓰기로 결정했기 때문에..
  * python에서 내장 sort가 엄청 빠른것을 생각하면, 카운팅소트로 바꿔도 기대보다는 그닥 성능 향상이 별로 크지 않을거 같다는 추측을 해본다

=== SA-IS 알고리즘 === 
  * Induced Sorting 을 이용하는 알고리즘이다.
  * [[https://en.wikipedia.org/wiki/Suffix_array#Construction_algorithms|위키피디아]]에 따르면 코드가 100줄도 안될정도로 간단하지만, 성능은 굉장히 좋다고 한다.
  * 코드 구현체는 여기저기서 찾을수 있다. [[https://github.com/cheran-senthil/PyRival/blob/master/pyrival/strings/suffix_array.py|PyRival]]에도 있고, [[https://judge.yosupo.jp/problem/suffixarray|Library checker]]에서 코드들을 뒤져봐도 몇몇 구현체를 찾을수 있다. [[https://gist.github.com/tjkendev/99d7330fe5642004b68268b31ba38ad4|주석이 달린 버전]]도 있다
    * 코드 자체는 정말로 길지 않다. PS에서 충분히 사용할수 있는 크기이다.
  * 문제는.. 알고리즘에 대해서 풀어서 설명을 해놓은 것을 찾기가 너무 힘들다. 
  * 대충 여기저기서 본것들을 종합하면, suffix들을 l-type과 s-type으로 분류하고, 그것들을 이용해서 문자열을 여러개의 LMS라 불리는 부분문자열로 나눈다. 그리고 각각의 LMS를 (재귀적으로) 정렬하고, 전체를 정렬한다..는 방식인거 같다
  * 근데 이렇게 하면 왜 되는지..에 관한 것들을 알기 위해서는 그냥 논문을 찾아보는 방법밖에 없을것 같다..
  * **설명을 찾았다!!** 그것도 무려 한국어. [[https://infossm.github.io/blog/2021/11/21/linear-suffix-array/]] 를 참고하자. 이거 진짜 귀한 자료다.. 영어로도 이런 설명 찾기 어렵다..

=== DC3 알고리즘 ===
  * 또다른 O(n)알고리즘이다. 위키피디아에서 3가지로 분류했던것중 Recursive algorithms 에 해당되는 알고리즘.
  * Skew 알고리즘이라고도 ㅂ른다
  * 이거는 그나마 좀 뒤져보면 설명해놓은 자료가 좀 있긴 하다. 자세히 읽지는 않았지만, 시작위치가 3의 배수가 아닌 서픽스들을 정렬하고 나면, 그것을 이용해서 O(n)에 3의 배수 서픽스를 정렬하고 머지할수 있다고 한다. 3의 배수가 아닌 서픽스들을 정렬하는 것을 재귀적으로 처리한다면 T(n) = T(2n/3)+O(n) 형태로 최종적으로 O(n)이 된다고 한다.
  * 하지만, 이쪽은 굴러다니는 코드를 찾기가 쉽지 않다; 실제로 SA-IS나 맨버-마이어스랑 비교해서 속도가 어떤지는 확인 못해봄. 
  * 이것도 [[https://infossm.github.io/blog/2021/11/21/linear-suffix-array/]]에 설명되어있다!!

==== LCP 배열 ====
  * Kasai's algoritm은 Suffix array 에서 LCP array를 O(n)에 구한다.
  * 알고리즘 자체는 매우 간단하다. 정당성은 조금 생각해봐야 할수도 있다.
  * [[https://cp-algorithms.com/string/suffix-array.html#longest-common-prefix-of-two-substrings-without-additional-memory]] 참고