prefixdoubling.cpp (2)

Bài toán

Tạo suffix array bằng phương pháp nhân đôi tiền tố.

Độ phức tạp

thời gian: O(n logn)

bộ nhớ: O(n)

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

#define long long long

#define f1(i, n) for (int i = 1; i <= n; i++)

#define f0(i, n) for (int i = 0; i < n; i++)

int cmp(int x, int y, int Rank[], int n, int k) {

    if (Rank[x] != Rank[y]) return Rank[x] - Rank[y];

    if (x + k > n || y + k > n) return x - y;

    return Rank[x + k] - Rank[y + k];

}

void radix_sort(int a[], int b[], int n, int r[], int K) {

    vector<int> Count(K + 1), Start(K + 1);

    f1(i, n) Count[r[a[i]]]++;

    f1(i, K) Start[i] = Start[i - 1] + Count[i - 1];

    f1(i, n) b[++Start[r[a[i]]]] = a[i];

}

void sort_suffix(int sa[], int Rank[], int n, int K) {  // 1-based

    int k = 1, *zz = new int[n + 1];

    for (;;) {

        radix_sort(sa, zz, n, Rank + k, K);

        radix_sort(zz, sa, n, Rank, K);

        K = 0;

        f1(i, n) {

            if (i == 1 || cmp(sa[i], sa[i - 1], Rank, n, k) != 0) K++;

            zz[sa[i]] = K;

        }

        f1(i, n) Rank[i] = zz[i];

        if (K == n) {

            delete[] zz;

            return;

        }

        k *= 2;

    }

}

#define N 100005

int n, Rank[2 * N], sa[2 * N];

char s[N];

main() {

    gets(s + 1);

    n = strlen(s + 1);

    f1(i, n) Rank[i] = s[i], sa[i] = i;

    sort_suffix(sa, Rank, n, 128);

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

}

Nhận xét

Code này đã được dùng để nộp cho một bài trên SPOJ

Tham khảo

http://www.spoj.com/problems/SARRAY/