04_week_suffix array, 맨버-마이어스

suffixt array란
접미사를 기준으로 sorting을 한다는 의미
접미사 배열은 아주 간단한 자료구조를 가지고
접미사 배열이 문자열 알고리즘에서 쓰이는 이유는
문자열 H가 문자열 N을 포함한다면 항상 N은 H의 어떤 접미사의 접두사라는 점을 이용한 부분

H의 접미사 배열을 이진탐색해서
각 문자열이 출현하는 위치를 찾을 수 있다

ex) SWJUNGLE

[0] SWJUNGLE
[1] WJUNGLE
[2] JUNGLE
[3] UNGLE
[4] NGLE
[5] GLE
[6] LE
[7] E

이를 제일 앞글자를 기준으로 사전 순으로 정렬하게 되면

[7] E
[5] GLE
[2] JUNGLE
[6] LE
[4] NGLE
[0] SWJUNGLE
[3] UNGLE
[1] WJUNGLE

이를 suffix array라고 부르며 부분 문자열을 찾는데 많이 사용된다

다른 예제들에는 중목되는 경우도 있다
아래 문서를 참고하였습니다

C++로 작성된 최종 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
vector<int> g,ng,sfx,cnt,orderToIdx;
vector<int> getsfx(string &s) {
    int n=s.size();
    int lim = max(257,n+1);
    g.resize(n+1); ng.resize(n+1); sfx.resize(n); orderToIdx.resize(n+1);
    for(int i=0; i<n; i++) sfx[i]=i, g[i]=s[i];
    for(int t=1; t<n; t<<=1) {
        cnt.clear(); cnt.resize(lim,0);
        for(int i=0; i<n; i++) cnt[g[min(i+t,n)]]++;
        for(int i=1; i<lim; i++) cnt[i]+=cnt[i-1];
        for(int idx=n-1; idx>=0; idx--) orderToIdx[--cnt[g[min(idx+t,n)]]]=idx;
        //orderToIdx[x]=idx; => pair에서 second기준으로 정렬했을 때, second기준으로 x번째에 해당하는 index는 idx라는 뜻이다.
 
        cnt.clear(); cnt.resize(lim,0);
        for(int i=0; i<n; i++) cnt[g[i]]++;
        for(int i=1; i<lim; i++) cnt[i]+=cnt[i-1];
        for(int i=n-1; i>=0; i--) sfx[--cnt[g[orderToIdx[i]]]]=orderToIdx[i];
        //sfx[x]=idx; => pair에서 second기준으로 정렬후 first기준으로 다시 stable sort를 했을 때, 순서로 x번째에 해당하는 인덱스는 idx라는 뜻이다.
 
        auto cmp = [&](int i, int j) {
            if(g[i]==g[j]) return g[i+t]<g[j+t];
            else return g[i]<g[j];
        };
        ng[sfx[0]]=1;
        for(int i=1; i<n; i++) {
            if(cmp(sfx[i-1],sfx[i])) ng[sfx[i]]=ng[sfx[i-1]]+1;
            else ng[sfx[i]]=ng[sfx[i-1]];
        }
        g=ng;
    }
    return sfx;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    string s; cin >> s;
    vector<int> sfx = getsfx(s);
    for(int i=0; i<sfx.size(); i++) {
        printf("%d ", sfx[i]);
    }
    return 0;
}

ref : 1. suffix array

맨버-마이어스의 알고리즘
가장 빠르지는 않지만 구현이 편한 알고리즘
이 알고리즘은 접미사들의 목록을 여러번 결정하고 매번 그 기준을 바꿈
처음에는 접미사 첫 한글자 (1)
두번째는 접미사 첫 두글자 (2)
세번째는 접미사 첫 네글자 (4)

이렇게 LogN번의 정렬을 반복하면 접미사 배열이 생성
2의 지수승으로 글자를 나눔
그 이유는
$\displaystyle\ 2^n=(2^{n-1}+2^{n-2}+...+ 1)+1$
이 식의 성립때문이라고 하는데 추가적인 공부가 필요함

ref : 2. suffix array