Submit Info #2991

Problem Lang User Status Time Memory
Suffix Array cpp okura AC 621 ms 8.82 MiB

ケース詳細
Name Status Time Memory
all_same_00 AC 492 ms 8.70 MiB
all_same_01 AC 494 ms 8.77 MiB
all_same_02 AC 493 ms 8.76 MiB
all_same_03 AC 493 ms 8.77 MiB
all_same_04 AC 493 ms 8.71 MiB
example_00 AC 4 ms 0.62 MiB
example_01 AC 7 ms 0.68 MiB
example_02 AC 6 ms 0.61 MiB
example_03 AC 5 ms 0.59 MiB
fib_str_00 AC 621 ms 8.81 MiB
fib_str_01 AC 428 ms 6.66 MiB
fib_str_02 AC 398 ms 6.36 MiB
fib_str_03 AC 360 ms 5.85 MiB
fib_str_04 AC 610 ms 8.68 MiB
max_random_00 AC 488 ms 8.71 MiB
max_random_01 AC 519 ms 8.77 MiB
max_random_02 AC 508 ms 8.82 MiB
max_random_03 AC 504 ms 8.79 MiB
max_random_04 AC 489 ms 8.67 MiB
random_00 AC 367 ms 7.02 MiB
random_01 AC 448 ms 8.30 MiB
random_02 AC 33 ms 1.47 MiB
random_03 AC 413 ms 7.67 MiB
random_04 AC 233 ms 5.19 MiB

#include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll; // #define int long long #define pb push_back #define mp make_pair #define eps 1e-9 #define INF 2000000000 #define LLINF 10000000000000ll #define fi first #define sec second #define all(x) (x).begin(),(x).end() #define sq(x) ((x)*(x)) #define dmp(x) cerr << #x << ": " << x << endl; template<class T> void chmin(T& a,const T& b){if(a>b)a=b;} template<class T> void chmax(T& a,const T& b){if(a<b)a=b;} template<class T> using MaxHeap = priority_queue<T>; template<class T> using MinHeap = priority_queue<T,vector<T>,greater<T> >; template<class T,class U> ostream& operator << (ostream& os,const pair<T,U>& p){ os << p.fi << ',' << p.sec; return os; } template<class T,class U> istream& operator >> (istream& is,pair<T,U>& p){ is >> p.fi >> p.sec; return is; } template<class T> ostream& operator << (ostream &os,const vector<T> &vec){ for(int i=0;i<vec.size();i++){ os << vec[i]; if(i+1<vec.size())os << ' '; } return os; } template<class T> istream& operator >> (istream &is,vector<T>& vec){ for(int i=0;i<vec.size();i++)is >> vec[i]; return is; } void fastio(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); } namespace Math{ template<int MOD> // if inv is needed, this shold be prime. struct ModInt{ ll val; ModInt():val(0ll){} ModInt(const ll& v):val(((v%MOD)+MOD)%MOD){} bool operator==(const ModInt& x)const{return val==x.val;} bool operator!=(const ModInt& x)const{return !(*this==x);} bool operator<(const ModInt& x)const{return val<x.val;} bool operator>(const ModInt& x)const{return val>x.val;} bool operator>=(const ModInt& x)const{return !(*this<x);} bool operator<=(const ModInt& x)const{return !(*this>x);} ModInt& operator+=(const ModInt& x){if((val+=x.val)>=MOD)val-=MOD;return *this;} ModInt& operator-=(const ModInt& x){if((val+=MOD-x.val)>=MOD)val-=MOD;return *this;} ModInt& operator*=(const ModInt& x){(val*=x.val)%=MOD;return *this;} ModInt operator+(const ModInt& x)const{return ModInt(*this)+=x;} ModInt operator-(const ModInt& x)const{return ModInt(*this)-=x;} ModInt operator*(const ModInt& x)const{return ModInt(*this)*=x;} friend istream& operator>>(istream&i,ModInt& x){ll v;i>>v;x=v;return i;} friend ostream& operator<<(ostream&o,const ModInt& x){o<<x.val;return o;} }; template<int MOD> ModInt<MOD> pow(ModInt<MOD> a,ll x){ ModInt<MOD> res = ModInt<MOD>(1ll); while(x){ if(x&1)res *= a; x >>= 1; a = a*a; } return res; } constexpr int MOD = 1e9+7; using mint = ModInt<MOD>; vector<mint> inv,fac,facinv; // notice: 0C0 = 1 ModInt<MOD> nCr(int n,int r){ assert(!(n<r)); assert(!(n<0||r<0)); return fac[n]*facinv[r]*facinv[n-r]; } void init(int SIZE){ fac.resize(SIZE+1); inv.resize(SIZE+1); facinv.resize(SIZE+1); fac[0] = inv[1] = facinv[0] = mint(1ll); for(int i=1;i<=SIZE;i++)fac[i]=fac[i-1]*mint(i); for(int i=2;i<=SIZE;i++)inv[i]=mint(0ll)-mint(MOD/i)*inv[MOD%i]; for(int i=1;i<=SIZE;i++)facinv[i]=facinv[i-1]*inv[i]; return; } template<class T> int digit(T x){ int res = 0; while(x){ x /= T(10); res++; } return res; } } namespace DS{ template<class T> struct RangeSum{ vector<T> vec; RangeSum(){} RangeSum(vector<T> elems):vec(elems){ for(int i=1;i<vec.size();i++){ vec[i] += vec[i-1]; } } T sum(int l,int r){ if(l>r)return T(0); if(l==0)return vec[r]; else return vec[r]-vec[l-1]; } }; template<class T> struct BIT{ int N; vector<T> bit; BIT(int N):N(N){ bit = vector<T>(N+1,T(0)); } void add(int i,T x){ i++; while(i<=N){ bit[i]+=x; i+=i&-i; } return; } T sum(int i){ i++; T res = T(0); while(i>0){ res+=bit[i]; i-=i&-i; } return res; } T sum(int l,int r){// [l,r] assert(l<=r); if(l==0)return sum(r); else return sum(r)-sum(l-1); } }; } namespace Util{ template<class T> struct SlideMin{ vector<T> v; deque<int> deq; SlideMin(vector<T> &v):v(v){} void add(int id){ while(!deq.empty()&&v[deq.back()]>=v[id])deq.pop_back(); deq.push_back(id); } T get(int id){ // [id,added] while(!deq.empty()&&deq.front()<id)deq.pop_front(); assert(!deq.empty()); return v[deq.front()]; } }; template<class T> struct SlideMax{ vector<T> v; deque<int> deq; SlideMax(vector<T> &v):v(v){} void add(int id){ while(!deq.empty()&&v[deq.back()]<=v[id])deq.pop_back(); deq.push_back(id); } T get(int id){ // [id,added] while(!deq.empty()&&deq.front()<id)deq.pop_front(); assert(!deq.empty()); return v[deq.front()]; } }; } struct SuffixArray{ string s; vector<int> sa; vector<int> rank; vector<int> lcp; explicit SuffixArray(string s):s(s){ int n = s.size(); sa.resize(n+1); rank.resize(n+1); vector<int> tmp(n+1); for(int i=0;i<=n;i++){ rank[i] = (i<n)?s[i]:-1; sa[i] = i; } for(int k=1;k<=n;k*=2){ auto compare_sa = [&](const int &i,const int &j){ if(rank[i]!=rank[j])return rank[i]<rank[j]; else{ int ri=(i+k<=s.size())?rank[i+k]:-1; int rj=(j+k<=s.size())?rank[j+k]:-1; return ri<rj; } }; sort(sa.begin(),sa.end(),compare_sa); tmp[sa[0]]=0; for(int i=1;i<=n;i++)tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0); for(int i=0;i<=n;i++)rank[i]=tmp[i]; } } size_t size() const { return s.size(); } int operator [] (int id) const { return sa[id]; } bool contain(string t){ int l = 0,r = s.size()+1; while(r-l>1){ int mid = (l+r)/2; if(s.compare(sa[mid],t.size(),t)<0){ l = mid; }else{ r = mid; } } return s.compare(sa[r],t.size(),t)==0; } }; signed main(){ fastio(); string s; cin >> s; SuffixArray sa(s); for(int i=1;i<=s.size();i++){ cout << sa[i]; if(i<s.size())cout << ' '; else cout << endl; } return 0; }