Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3655

Problem Lang User Status Time Memory
Suffix Array cpp suzuken AC 235 ms 14.50 MiB

ケース詳細
Name Status Time Memory
all_same_00 AC 119 ms 14.38 MiB
all_same_01 AC 121 ms 14.48 MiB
all_same_02 AC 122 ms 14.42 MiB
all_same_03 AC 121 ms 14.43 MiB
all_same_04 AC 120 ms 14.38 MiB
example_00 AC 6 ms 0.62 MiB
example_01 AC 6 ms 0.66 MiB
example_02 AC 5 ms 0.62 MiB
example_03 AC 6 ms 0.66 MiB
fib_str_00 AC 197 ms 14.50 MiB
fib_str_01 AC 141 ms 10.85 MiB
fib_str_02 AC 129 ms 10.30 MiB
fib_str_03 AC 113 ms 9.61 MiB
fib_str_04 AC 192 ms 14.26 MiB
max_random_00 AC 233 ms 14.38 MiB
max_random_01 AC 235 ms 14.43 MiB
max_random_02 AC 235 ms 14.43 MiB
max_random_03 AC 234 ms 14.47 MiB
max_random_04 AC 233 ms 14.31 MiB
random_00 AC 178 ms 11.50 MiB
random_01 AC 218 ms 13.59 MiB
random_02 AC 20 ms 2.22 MiB
random_03 AC 200 ms 12.63 MiB
random_04 AC 122 ms 8.39 MiB

#pragma GCC optimize("O3") #include<bits/stdc++.h> using namespace std; using ll=long long; using P=pair<ll,ll>; template<class T> using V=vector<T>; #define fi first #define se second #define all(v) (v).begin(),(v).end() const ll inf=(1e18); const ll mod=1000000007; //const ll mod=998244353; ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;} ll lcm(ll c,ll d){return c/gcd(c,d)*d;} struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init; template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } struct SA{ V<int> sa,as,lcp; int n; SA(const string &s){ n=s.size();sa.assign(n,0);as.assign(n,0);lcp.assign(n-1,0); for(int i=0;i<n;i++)sa[i]=n-1-i; sort(all(sa),[&](const int a,const int b){return (s[a]==s[b]?(a>b):(s[a]<s[b]));}); V<int> c(n); for(int i=0;i<n;i++)c[i]=s[i]; for(int len=1;len<n;len<<=1){ V<int> d=c; for(int i=0;i<n;i++){ if(i>0&&sa[i-1]+len<n&&d[sa[i-1]]==d[sa[i]]&&d[sa[i-1]+len/2]==d[sa[i]+len/2]){ c[sa[i]]=c[sa[i-1]]; } else{ c[sa[i]]=i; } } V<int> cp=sa,f(n); iota(all(f),0); for(int i=0;i<n;i++){ int j=cp[i]-len; if(j>=0)sa[f[c[j]]++]=j; } } } }; int main(){ string s; cin>>s; SA sa(s); for(int v:sa.sa)cout<<v<<" "; cout<<"\n"; }