UVA – 00719 – Glass Beads – [Suffix Array]

#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 100100;

struct SuffixArray {
	pair<int, int> sf[MAXN];
	int sa[MAXN], r[MAXN], height[MAXN], h[MAXN];

	struct mycmp {
		pair<int, int> * suffix;
		mycmp(pair<int, int> * suffix_) :
			suffix(suffix_) {
		}
		bool operator()(int lhs, int rhs) {
			return suffix[lhs] < suffix[rhs];
		}
	};

	void init(int n, const char a[MAXN]) {
		sa[0] = 0; // n = 1
		for (int i = 0; i < n; ++i)
			r[i] = a[i];
		for (int i, m = 1; m < n; m <<= 1) {
			for (i = 0; i < n; sa[i] = i++)
				sf[i] = make_pair(r[i], r[(i + m) % n]);
			stable_sort(sa, sa + n, mycmp(sf));
			for (i = 1, r[sa[0]] = 0; i < n; ++i)
				r[sa[i]] = sf[sa[i]] != sf[sa[i - 1]] ? i : r[sa[i - 1]];
		}
	}
} sa;

int main() {
	char s[100003];
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%s", s);
		int len = strlen(s);
		sa.init(len, s);
		printf("%d\n", sa.sa[0] + 1);

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

%d bloggers like this: