Suffix Array

Đề bài: http://www.spoj.com/problems/SARRAY/

Code C++: 0-based index

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define MAXN 100005
char T[MAXN];
int n, k;
int sa[MAXN], ra[MAXN], rb[MAXN];

bool cmp(int i, int j) {
    return (ra[i] < ra[j]) ||
           (ra[i] == ra[j] && ra[i+k] < ra[j+k]);
}

int main() {
    n = strlen(gets(T));
    for(int i = 0; i < n; i++) sa[i] = i;
    for(int i = 0; i < n; i++) ra[i] = T[i];
    for(k = 1; k < n; k <<= 1) {
        sort(sa, sa+n, cmp);
        // we index rank from 1 (to n) to make all rank value 
        // greater than the rest of ra array (which is 0 by default)
        rb[sa[0]] = 1;
        for(int i = 1; i < n; i++)
            rb[sa[i]] = rb[sa[i-1]] + cmp(sa[i-1], sa[i]);
        for(int i = 0; i < n; i++)
            ra[sa[i]] = rb[sa[i]];
        if (ra[sa[n-1]] == n) break;
    }
    
    for(int i = 0; i < n; i++) printf("%d\n", sa[i]);
    
    return 0;
}

Độ phức tạp: O(N*log^2N)

Happy coding,

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s