src/string/sa.hpp

View this file on GitHub
Last update: 2026-01-07 21:13:29+09:00
Include: #include "src/string/sa.hpp"

Depends on

src/template.hpp

Code

#pragma once
#include "../template.hpp"

vector<int> suffix_array(string S){
    int N=si(S);
    vector<int> rank(N+1),tmp(N+1),sa(N+1);
    rep(i,N+1){
        sa[i]=i;
        rank[i]=i<N?S[i]:-1;
    }
    for(int k=1;k<=N;k*=2){
        auto comp=[&](int i,int j) {
            if(rank[i]!=rank[j]) return rank[i]<rank[j];
            int ri=(i+k<=N)?rank[i+k]:-1;
            int rj=(j+k<=N)?rank[j+k]:-1;
            return ri<rj;
        };
        sort(all(sa),comp);
        tmp[sa[0]]=0;
        for(int i=1;i<=N;i++){
            tmp[sa[i]]=tmp[sa[i-1]]+(comp(sa[i-1],sa[i])?1:0);
        }
        rep(i,N+1){
            rank[i]=tmp[i];
        }
    }
    sa.erase(sa.begin());
    return sa;
}

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 3 "src/string/sa.hpp"

vector<int> suffix_array(string S){
    int N=si(S);
    vector<int> rank(N+1),tmp(N+1),sa(N+1);
    rep(i,N+1){
        sa[i]=i;
        rank[i]=i<N?S[i]:-1;
    }
    for(int k=1;k<=N;k*=2){
        auto comp=[&](int i,int j) {
            if(rank[i]!=rank[j]) return rank[i]<rank[j];
            int ri=(i+k<=N)?rank[i+k]:-1;
            int rj=(j+k<=N)?rank[j+k]:-1;
            return ri<rj;
        };
        sort(all(sa),comp);
        tmp[sa[0]]=0;
        for(int i=1;i<=N;i++){
            tmp[sa[i]]=tmp[sa[i-1]]+(comp(sa[i-1],sa[i])?1:0);
        }
        rep(i,N+1){
            rank[i]=tmp[i];
        }
    }
    sa.erase(sa.begin());
    return sa;
}