SPOJ – 705 – New Distinct Substrings – [Suffix Arrays nlgn]

#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
 
using namespace std;
 
//  O(n log n) - Manber and Myers 
 
#define N 1000005
char str[N]; //input
int rank[N], pos[N]; //output

int cnt[N], next[N]; 
bool bh[N], b2h[N];
 

bool smaller_first_char(int a, int b) {
	return str[a] < str[b];
}
 
void suffixSort(int n) {
	for (int i = 0; i < n; ++i) {
		pos[i] = i;
	}
	sort(pos, pos + n, smaller_first_char);

 
	for (int i = 0; i < n; ++i) {
		bh[i] = i == 0 || str[pos[i]] != str[pos[i - 1]];
		b2h[i] = false;
	}
 
	for (int h = 1; h < n; h <<= 1) {
		int buckets = 0;
		for (int i = 0, j; i < n; i = j) {
			j = i + 1;
			while (j < n && !bh[j])
				j++;
			next[i] = j;
			buckets++;
		}
		if (buckets == n)
			break; 

 
		for (int i = 0; i < n; i = next[i]) {
			cnt[i] = 0;
			for (int j = i; j < next[i]; ++j) {
				rank[pos[j]] = i;
			}
		}
 
		cnt[rank[n - h]]++;
		b2h[rank[n - h]] = true;
		for (int i = 0; i < n; i = next[i]) {
			for (int j = i; j < next[i]; ++j) {
				int s = pos[j] - h;
				if (s >= 0) {
					int head = rank[s];
					rank[s] = head + cnt[head]++;
					b2h[rank[s]] = true;
				}
			}
			for (int j = i; j < next[i]; ++j) {
				int s = pos[j] - h;
				if (s >= 0 && b2h[rank[s]]) {
					for (int k = rank[s] + 1; !bh[k] && b2h[k]; k++)
						b2h[k] = false;
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			pos[rank[i]] = i;
			bh[i] |= b2h[i];
		}
	}
	for (int i = 0; i < n; ++i) {
		rank[pos[i]] = i;
	}
}
 
 
// O(n) - lcp - "Arrays and Its Applications" by Toru Kasai, Gunho Lee

int height[N];
// height[i] = lcp of suffix pos[i] and suffix pos[i-1]
// height[0] = 0
void getHeight(int n) {
	for (int i = 0; i < n; ++i)
		rank[pos[i]] = i;
	height[0] = 0;
	for (int i = 0, h = 0; i < n; ++i) {
		if (rank[i] > 0) {
			int j = pos[rank[i] - 1];
			while (i + h < n && j + h < n && str[i + h] == str[j + h])
				h++;
			height[rank[i]] = h;
			if (h > 0)
				h--;
		}
	}
}

 
int main() {
	string s;
	int T;
	scanf("%d", &T);
	gets(str);
	while (T--) {
		gets(str);
		long long len = 0LL + strlen(str);
		long long total = len*(len+1)/2;
		suffixSort(len);
		getHeight(len);
 
		for (int i = 0; i < len; i++) 
			total -=   height[i];
		
		cout << total << endl;
	}
}

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: