prefixdoubling.cpp (3)

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

using namespace std;

const int N = 200005;

char a[N];

int n;

int sa[N], ra[N], Diff[N];

struct cmp {

    int *h, Gap;

    cmp(int* h, int Gap) : h(h), Gap(Gap) {}

    bool operator()(int x, int y) { return h[x] != h[y] ? h[x] < h[y] : h[x + Gap] < h[y + Gap]; }

};

void suffix_array() {

    for (int i = 1; i <= n; i++) {

        sa[i] = i;

        ra[i] = a[i];

    }

    int MaxRA = 256, Gap = 1;

    do {

        sort(sa + 1, sa + n + 1, cmp(ra, Gap));

        for (int i = 1; i <= n; i++) {

            Diff[i] = i == 1 || ra[sa[i]] != ra[sa[i - 1]] || ra[sa[i] + Gap] != ra[sa[i - 1] + Gap];

        }

        MaxRA = 0;

        for (int i = 1; i <= n; i++)

            ra[sa[i]] = (Diff[i] ? ++MaxRA : MaxRA);

        Gap *= 2;

    } while (MaxRA != n);

}

int main() {

    scanf("%s", a + 1);

    n = strlen(a + 1);

    suffix_array();

    for (int i = 1; i <= n; i++)

        printf("%d\n", sa[i] - 1);

}