代码

/*****************************************************************************/

#define _M_Size (1 << 24)
char _M[_M_Size];
char* _M_pos = _M + _M_Size;

/* sais.c for sais-lite (edited) *********************************************/

#define elsif else if

#ifndef MINBUCKETSIZE
# define MINBUCKETSIZE 256
#endif

#define sais_index_type int
#define sais_bool_type  int
#define SAIS_LMSSORT2_LIMIT 0x3fffffff

#define sais_malloc(_num, _type) (_type *)(_M_pos -= ((_num) * sizeof(_type)))

/* find the start or end of each bucket */
inline void getCounts(sais_index_type T[], sais_index_type C[], sais_index_type n, sais_index_type k)
{
	sais_index_type i;
	for (i = 0; i < k; ++i)
		C[i] = 0;
	for (i = 0; i < n; ++i)
		++C[T[i]];
}

inline void getBuckets(sais_index_type C[], sais_index_type B[], sais_index_type k, sais_bool_type end)
{
	sais_index_type i, sum = 0;
	if (end)
		for (i = 0; i < k; ++i)
			B[i] = sum += C[i];
	else
		for (i = 0; i < k; ++i)
			sum += C[i], B[i] = sum - C[i];
}

/* sort all type LMS suffixes */
inline void LMSsort1(sais_index_type T[], sais_index_type SA[], sais_index_type C[], sais_index_type B[], sais_index_type n, sais_index_type k)
{
	sais_index_type *b, i, j;
	sais_index_type c0, c1;
	
	/* compute SAl */
	if (C == B)
		getCounts(T, C, n, k);
	getBuckets(C, B, k, 0); /* find starts of buckets */
	j = n - 1;
	b = SA + B[c1 = T[j]];
	--j;
	*b++ = (T[j] < c1) ? ~j : j;
	for (i = 0; i < n; ++i)
	{
		if (0 < (j = SA[i]))
		{
			if ((c0 = T[j]) != c1)
				B[c1] = b - SA, b = SA + B[c1 = c0];
			--j;
			*b++ = (T[j] < c1) ? ~j : j;
			SA[i] = 0;
		}
		elsif (j < 0)
			SA[i] = ~j;
	}
	/* compute SAs */
	if (C == B)
		getCounts(T, C, n, k);
	getBuckets(C, B, k, 1); /* find ends of buckets */
	for (i = n - 1, b = SA + B[c1 = 0]; 0 <= i; --i)
		if (0 < (j = SA[i]))
		{
			if ((c0 = T[j]) != c1)
				B[c1] = b - SA, b = SA + B[c1 = c0];
			--j;
			*--b = (T[j] > c1) ? ~(j + 1) : j;
			SA[i] = 0;
		}
}

inline sais_index_type LMSpostproc1(sais_index_type T[], sais_index_type SA[], sais_index_type n, sais_index_type m)
{
	sais_index_type i, j, p, q, plen, qlen, name;
	sais_index_type c0, c1;
	sais_bool_type diff;
	
	/* compact all the sorted substrings into the first m items of SA
	2*m must be not larger than n (proveable) */
	for (i = 0; (p = SA[i]) < 0; ++i)
		SA[i] = ~p;
	if (i < m)
		for (j = i, ++i; ; ++i)
			if ((p = SA[i]) < 0)
			{
				SA[j++] = ~p, SA[i] = 0;
				if (j == m)
					break;
			}
	
	/* store the length of all substrings */
	i = n - 1; j = n - 1; c0 = T[n - 1];
	do
		c1 = c0;
	while ((0 <= --i) && ((c0 = T[i]) >= c1));
	for (; 0 <= i; )
	{
		do
			c1 = c0;
		while ((0 <= --i) && ((c0 = T[i]) <= c1));
		if (0 <= i)
		{
			SA[m + ((i + 1) >> 1)] = j - i; j = i + 1;
			do
				c1 = c0;
			while ((0 <= --i) && ((c0 = T[i]) >= c1));
		}
	}
	
	/* find the lexicographic names of all substrings */
	for (i = 0, name = 0, q = n, qlen = 0; i < m; ++i)
	{
		p = SA[i], plen = SA[m + (p >> 1)], diff = 1;
		if ((plen == qlen) && ((q + plen) < n))
		{
			for (j = 0; (j < plen) && (T[p + j] == T[q + j]); ++j)
				;
			if (j == plen)
				diff = 0;
		}
		if (diff)
			++name, q = p, qlen = plen;
		SA[m + (p >> 1)] = name;
	}
	
	return name;
}

inline void LMSsort2(sais_index_type T[], sais_index_type SA[], sais_index_type C[], sais_index_type B[], sais_index_type D[], sais_index_type n, sais_index_type k)
{
	sais_index_type *b, i, j, t, d;
	sais_index_type c0, c1;
	
	/* compute SAl */
	getBuckets(C, B, k, 0); /* find starts of buckets */
	j = n - 1;
	b = SA + B[c1 = T[j]];
	--j;
	t = (T[j] < c1);
	j += n;
	*b++ = (t & 1) ? ~j : j;
	for (i = 0, d = 0; i < n; ++i)
	{
		if (0 < (j = SA[i]))
		{
			if (n <= j)
				++d, j -= n;
			if ((c0 = T[j]) != c1)
				B[c1] = b - SA, b = SA + B[c1 = c0];
			--j;
			t = c0; t = (t << 1) | (T[j] < c1);
			if (D[t] != d)
				j += n, D[t] = d;
			*b++ = (t & 1) ? ~j : j;
			SA[i] = 0;
		}
		elsif (j < 0)
			SA[i] = ~j;
	}
	for (i = n - 1; 0 <= i; --i)
		if (0 < SA[i] && SA[i] < n)
		{
			SA[i] += n;
			for (j = i - 1; SA[j] < n; --j)
				;
			SA[j] -= n;
			i = j;
		}
	
	/* compute SAs */
	getBuckets(C, B, k, 1); /* find ends of buckets */
	for (i = n - 1, d += 1, b = SA + B[c1 = 0]; 0 <= i; --i)
		if (0 < (j = SA[i]))
		{
			if (n <= j)
				++d, j -= n;
			if ((c0 = T[j]) != c1)
				B[c1] = b - SA, b = SA + B[c1 = c0];
			--j;
			t = c0; t = (t << 1) | (T[j] > c1);
			if (D[t] != d)
				j += n, D[t] = d;
			*--b = (t & 1) ? ~(j + 1) : j;
			SA[i] = 0;
		}
}

inline sais_index_type LMSpostproc2(sais_index_type SA[], sais_index_type n, sais_index_type m)
{
	sais_index_type i, j, d, name;
	
	/* compact all the sorted LMS substrings into the first m items of SA */
	for (i = 0, name = 0; (j = SA[i]) < 0; ++i)
	{
		j = ~j;
		if (n <= j)
			++name;
		SA[i] = j;
	}
	if (i < m)
		for (d = i, ++i; ; ++i)
			if ((j = SA[i]) < 0)
			{
				j = ~j;
				if (n <= j)
					++name;
				SA[d++] = j;
				SA[i] = 0;
				if (d == m)
					break;
			}
	if (name < m)
		/* store the lexicographic names */
		for (i = m - 1, d = name + 1; 0 <= i; --i)
		{
			if (n <= (j = SA[i]))
				j -= n, --d;
			SA[m + (j >> 1)] = d;
		}
	else
		/* unset flags */
		for (i = 0; i < m; ++i)
			if (n <= (j = SA[i]))
				j -= n, SA[i] = j;
	
	return name;
}

/* compute SA and BWT */
inline void induceSA(sais_index_type T[], sais_index_type SA[], sais_index_type C[], sais_index_type B[], sais_index_type n, sais_index_type k)
{
	sais_index_type *b, i, j;
	sais_index_type c0, c1;
	/* compute SAl */
	if (C == B)
		getCounts(T, C, n, k);
	getBuckets(C, B, k, 0); /* find starts of buckets */
	j = n - 1;
	b = SA + B[c1 = T[j]];
	*b++ = ((0 < j) && (T[j - 1] < c1)) ? ~j : j;
	for (i = 0; i < n; ++i)
	{
		j = SA[i], SA[i] = ~j;
		if (0 < j)
		{
			--j;
			if ((c0 = T[j]) != c1)
				B[c1] = b - SA, b = SA + B[c1 = c0];
			*b++ = ((0 < j) && (T[j - 1] < c1)) ? ~j : j;
		}
	}
	/* compute SAs */
	if (C == B)
		getCounts(T, C, n, k);
	getBuckets(C, B, k, 1); /* find ends of buckets */
	for (i = n - 1, b = SA + B[c1 = 0]; 0 <= i; --i)
		if (0 < (j = SA[i]))
		{
			--j;
			if ((c0 = T[j]) != c1)
				B[c1] = b - SA, b = SA + B[c1 = c0];
			*--b = ((j == 0) || (T[j - 1] > c1)) ? ~j : j;
		}
		else
			SA[i] = ~j;
}

/* find the suffix array SA of T[0..n-1] in {0..255}^n */
inline sais_index_type sais_main(sais_index_type T[], sais_index_type SA[], sais_index_type fs, sais_index_type n, sais_index_type k)
{
	sais_index_type *C, *B, *D, *RA, *b;
	sais_index_type i, j, m, p, q, t, name, pidx = 0, newfs;
	sais_index_type c0, c1;
	unsigned int flags;
	
	if (k <= MINBUCKETSIZE)
	{
		C = sais_malloc(k, sais_index_type);
		if (k <= fs)
			B = SA + (n + fs - k), flags = 1;
		else
			B = sais_malloc(k, sais_index_type), flags = 3;
	}
	else
		if (k <= fs)
		{
			C = SA + (n + fs - k);
			if (k <= (fs - k))
				B = C - k, flags = 0;
			elsif (k <= (MINBUCKETSIZE * 4))
				B = sais_malloc(k, sais_index_type), flags = 2;
			else
				B = C, flags = 8;
		}
		else
			C = B = sais_malloc(k, sais_index_type), flags = 4 | 8;
	if ((n <= SAIS_LMSSORT2_LIMIT) && (2 <= (n / k)))
	{
		if (flags & 1)
			flags |= ((k * 2) <= (fs - k)) ? 32 : 16;
		elsif ((flags == 0) && ((k * 2) <= (fs - k * 2)))
			flags |= 32;
	}
	
	/* stage 1: reduce the problem by at least 1/2
	sort all the LMS-substrings */
	getCounts(T, C, n, k), getBuckets(C, B, k, 1); /* find ends of buckets */
	for (i = 0; i < n; ++i)
		SA[i] = 0;
	b = &t, i = n - 1, j = n, m = 0, c0 = T[n - 1];
	do
		c1 = c0;
	while ((0 <= --i) && ((c0 = T[i]) >= c1));
	for (; 0 <= i; )
	{
		do
			c1 = c0;
		while ((0 <= --i) && ((c0 = T[i]) <= c1));
		if (0 <= i)
		{
			*b = j; b = SA + --B[c1]; j = i; ++m;
			do
				c1 = c0;
			while ((0 <= --i) && ((c0 = T[i]) >= c1));
		}
	}
	
	if (1 < m)
	{
		if (flags & (16 | 32))
		{
			if (flags & 16)
				D = sais_malloc(k * 2, sais_index_type);
			else
				D = B - k * 2;
			++B[T[j + 1]];
			for (i = 0, j = 0; i < k; ++i)
			{
				j += C[i];
				if (B[i] != j)
					SA[B[i]] += n;
				D[i] = D[i + k] = 0;
			}
			LMSsort2(T, SA, C, B, D, n, k);
			name = LMSpostproc2(SA, n, m);
		}
		else
		{
			LMSsort1(T, SA, C, B, n, k);
			name = LMSpostproc1(T, SA, n, m);
		}
	}
	elsif (m == 1)
		*b = j + 1, name = 1;
	else
		name = 0;
	
	/* stage 2: solve the reduced problem
	recurse if names are not yet unique */
	if (name < m)
	{
		newfs = (n + fs) - (m * 2);
		if ((flags & (1 | 4 | 8)) == 0)
		{
			if ((k + name) <= newfs)
				newfs -= k;
			else
				flags |= 8;
		}
		RA = SA + m + newfs;
		for (i = m + (n >> 1) - 1, j = m - 1; m <= i; --i)
			if (SA[i] != 0)
				RA[j--] = SA[i] - 1;
		sais_main(RA, SA, newfs, m, name);
		
		i = n - 1; j = m - 1; c0 = T[n - 1];
		do
			c1 = c0;
		while ((0 <= --i) && ((c0 = T[i]) >= c1));
		for (; 0 <= i; )
		{
			do
				c1 = c0;
			while ((0 <= --i) && ((c0 = T[i]) <= c1));
			if (0 <= i)
			{
				RA[j--] = i + 1;
				do
					c1 = c0;
				while ((0 <= --i) && ((c0 = T[i]) >= c1));
			}
		}
		for (i = 0; i < m; ++i)
			SA[i] = RA[SA[i]];
		if (flags & 4)
			C = B = sais_malloc(k, int);
		if (flags & 2)
			B = sais_malloc(k, int);
	}
	
	/* stage 3: induce the result for  the original problem */
	if (flags & 8)
		getCounts(T, C, n, k);
	/* put all left-most S characters into their buckets */
	if (1 < m)
	{
		getBuckets(C, B, k, 1); /* find ends of buckets */
		i = m - 1, j = n, p = SA[m - 1], c1 = T[p];
		do
		{
			q = B[c0 = c1];
			while (q < j)
				SA[--j] = 0;
			do
			{
				SA[--j] = p;
				if (--i < 0)
					break;
				p = SA[i];
			}
			while ((c1 = T[p]) == c0);
		}
		while (0 <= i);
		while (0 < j)
			SA[--j] = 0;
	}
	induceSA(T, SA, C, B, n, k);
	
	return pidx;
}

/*---------------------------------------------------------------------------*/

inline int sais(int T[], int SA[], int n)
{
	return sais_main(T, SA, 0, n, 128);
}

/*****************************************************************************/

#include <stdio.h>
#include <string.h>

#define _O_Buffer_Size (1 << 24)
char _O_Buffer[_O_Buffer_Size];
char* _O_pos = _O_Buffer;

inline void putint(int x)
{
	char _buf[10];
	char* _pos = _buf;
	do
		*_pos++ = x % 10 | '0';
	while (x /= 10);
	while (_pos != _buf)
		*_O_pos++ = *--_pos;
}

/*---------------------------------------------------------------------------*/

#define Size 100005

int length;
char buf[Size];
int S[Size];
int SA[Size];
int Rank[Size];
int LCP[Size];

int main(int argc, char** argv)
{
	fread(buf, 1, Size, stdin);
	for (length = 0; 'a' <= buf[length] && buf[length] <= 'z'; ++length)
		S[length] = buf[length];
	
	sais(S, SA,length + 1);
	
	int i, j;
	for (i = 1; i <= length; ++i)
		putint(SA[i] + 1), *_O_pos++ = ' ';
	*_O_pos++ = '\n';
	
	for (i = 0; i <= length; ++i)
		Rank[SA[i]] = i;
	
	for (i = j = 0; i <= length; ++i)
		if (Rank[i])
		{
			while (S[SA[Rank[i]] + j] == S[SA[Rank[i] - 1] + j])
				++j;
			LCP[Rank[i]] = j;
			if (j)
				--j; 
		}
	
	for (i = 2; i <= length; ++i)
		putint(LCP[i]), *_O_pos++ = ' ';
	*_O_pos++ = '\n';
	
	fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout);
	
	return 0;
}

评测结果