#include "string/suffix_array.hpp"
#pragma once #include<string> #include<vector> #include<algorithm> #include <numeric> #include<cmath> /** * @brief SuffixArray */ std::vector<int> suffix_array(std::string s){ int n=s.size(); std::vector<int> v1(n,-1),v2(n,-1); std::vector<int> rank(n,-1); std::iota(v1.begin(),v1.end(),0); std::iota(v2.begin(),v2.end(),0); std::sort(v1.begin(),v1.end(),[&](auto p,auto q){return s[p]<s[q];}); int idx=0; for(int i=0;i<n;++i){ rank[v1[i]]=idx; if(i<n-1&&s[v1[i]]!=s[v1[i+1]])idx++; } for(int i=0;i<(int)std::log2(n)+2;++i){ const int h=1<<i; std::sort(v2.begin(),v2.end(),[&](auto p,auto q){ return make_pair(rank[p],p+h<n?rank[p+h]:-1)<make_pair(rank[q],q+h<n?rank[q+h]:-1); }); swap(v1,v2); idx=0; std::vector<int> tmp(n,-1); for(int j=0;j<n;++j){ tmp[v1[j]]=idx; if(j<n-1&&std::make_pair(rank[v1[j]],v1[j]+h<n?rank[v1[j]+h]:-1)<std::make_pair(rank[v1[j+1]],v1[j+1]+h<n?rank[v1[j+1]+h]:-1))idx++; } std::swap(rank,tmp); } return v1; }
#line 2 "string/suffix_array.hpp" #include<string> #include<vector> #include<algorithm> #include <numeric> #include<cmath> /** * @brief SuffixArray */ std::vector<int> suffix_array(std::string s){ int n=s.size(); std::vector<int> v1(n,-1),v2(n,-1); std::vector<int> rank(n,-1); std::iota(v1.begin(),v1.end(),0); std::iota(v2.begin(),v2.end(),0); std::sort(v1.begin(),v1.end(),[&](auto p,auto q){return s[p]<s[q];}); int idx=0; for(int i=0;i<n;++i){ rank[v1[i]]=idx; if(i<n-1&&s[v1[i]]!=s[v1[i+1]])idx++; } for(int i=0;i<(int)std::log2(n)+2;++i){ const int h=1<<i; std::sort(v2.begin(),v2.end(),[&](auto p,auto q){ return make_pair(rank[p],p+h<n?rank[p+h]:-1)<make_pair(rank[q],q+h<n?rank[q+h]:-1); }); swap(v1,v2); idx=0; std::vector<int> tmp(n,-1); for(int j=0;j<n;++j){ tmp[v1[j]]=idx; if(j<n-1&&std::make_pair(rank[v1[j]],v1[j]+h<n?rank[v1[j]+h]:-1)<std::make_pair(rank[v1[j+1]],v1[j+1]+h<n?rank[v1[j+1]+h]:-1))idx++; } std::swap(rank,tmp); } return v1; }