mayoko’s diary

プロコンとかいろいろ。

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;
}