AtCoder Regular Contest 050 D - Suffix Concat(その 2)
解法
これを参考に RollingHash でも解いてみました。
topcoder.g.hatena.ne.jp
考え方(ソートの仕方)はさっきと同じです。問題なのは, RollingHash を使ってどうやってソートをするか, ということなんですが,
s.substr(lhs), s.substr(rhs) の共通接頭辞は何文字かを二分探索で求め, 文字同士を直接比較すればいけます。
const int MAXN = 100010; struct RollingHash { static const ll mul0=10009,mul1=10007; static const ll add0=1000010007, add1=1003333331; string s; int l; vector<ll> hash_,pmo_; void init(string s) { this->s=s; l=s.size(); hash_.resize(l+1); pmo_.resize(l+1); hash_[0]=0; pmo_[0]=1; for (int i = 0; i < l; i++) pmo_[i+1]=pmo_[i]*mul0; for (int i = 0; i < l; i++) hash_[i+1]=(hash_[i]*mul0+add0+s[i]); } ll hash(int l,int r) { // s[l..r) return hash_[r]-hash_[l]*pmo_[r-l]; } }; RollingHash rh; string s; int N; int perm[MAXN]; int sameLen(int lhs, int rhs) { int low = 0, high = N-rhs+1; while (high-low > 1) { const int med = (low+high)/2; if (rh.hash(lhs, lhs+med) == rh.hash(rhs, rhs+med)) low = med; else high = med; } return low; } bool compare(int lhs, int rhs) { bool flip = false; if (lhs > rhs) { flip = true; swap(lhs, rhs); } int len = sameLen(lhs, rhs); if (len < N-rhs) return flip ^ (s[lhs+len] < s[rhs+len]); int exLen = sameLen(lhs, lhs+len); return flip ^ (s[lhs+len+exLen] < s[lhs+exLen]); } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N; cin >> s; for (int i = 0; i < N; i++) perm[i] = i; rh.init(s); sort(perm, perm+N, compare); for (int i = 0; i < N; i++) cout << perm[i]+1 << endl; return 0; }