Suffix automaton으로 Suffix tree 만들기

sa + lcp로 만드는 것과 무엇이 다를까

아무튼 만들었으니 된거다.

Suffix automaton 코드는 구사과님 코드에서 따왔다.

 

+ 250627 주석 추가

#define sz(v) (int)v.size()
#define fi first
#define se second
#define pii pair<int, int>

const int mxA = 26; // 문자 개수
struct SuffixTree 
/*
	0번 정점은 루트 노드, 부모는 -1
	i번 정점은 s를 1-base로 보았을 때 s[i..n]가 끝나는 위치(깊이가 모두 달라서 겹칠 우려 없음)
	child[i]에 i번 정점의 자식 vector
	i번 정점의 parent는 sa[i].slink
	rng[i]는 i번 정점과 부모를 잇는 substring에 대응하는 구간 (s[rng[i].fi, rng[i].se])
	문자 개수가 많은 경우에는 nxt를 map<int, int>로 바꿔주면 된다.
*/

{
    struct node {
        int nxt[mxA], len, slink;
        node() {
            memset(nxt, -1, sizeof(nxt));
            len = slink = 0;
        }
        node(int _len, int _slink) {
            memset(nxt, -1, sizeof(nxt));
            len = _len;
            slink = _slink;
        }
    };
    int n;
    vector<node> sa;
    int total;
    void addChar(int c, int pos) {
        assert(0 <= c && c < mxA);
        sa[pos] = node(sa[total].len + 1, 0);
        int p = total;
        total = pos;
        while (p != -1 && sa[p].nxt[c] == -1) {
            sa[p].nxt[c] = total;
            p = sa[p].slink;
        }
        if (p != -1) {
            int prv = sa[p].nxt[c];
            int upd = sa[p].nxt[c];
            if (sa[p].len + 1 < sa[prv].len) {
                upd = sz(sa);
                node nd = sa[prv];
                nd.len = sa[p].len + 1;
                sa.push_back(nd);
                sa[prv].slink = upd;
                for (int j = p; j != -1 && sa[j].nxt[c] == prv; j = sa[j].slink) {
                    sa[j].nxt[c] = upd;
                }
            }
            sa[total].slink = upd;
        }
    }
    vector<vector<int>> child;
    vector<pii> rng;
    void dfs(int now) {
        int par = sa[now].slink;
        int nlen = sa[now].len - (par == -1 ? 0 : sa[par].len);
        if (child[now].empty()) {
            rng[now] = pii(n - nlen + 1, n);
            return;
        }
        for (int nxt : child[now]) dfs(nxt);
        int nxt = child[now][0];
        rng[now] = pii(rng[nxt].fi - nlen, rng[nxt].fi - 1);
    }
    SuffixTree(string s) {
        // Suffix automaton start
        total = 0;
        // sa.reserve(2000001);
        sa.push_back(node(0, -1));
        // Suffix automaton end

        // Suffix tree start
        n = sz(s);
        sa.resize(n + 1);
        for (int i = n - 1; i >= 0; i--) addChar(s[i]-'a', i + 1);
        child.resize(sz(sa));
        rng.resize(sz(sa));
        for (int i = 1; i < sz(sa); i++) child[sa[i].slink].push_back(i);
        dfs(0);
    }
    SuffixTree() {}
};