poj 2774 后缀数组

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

#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

#define maxn 200004
#define MIN(a, b) (a) < (b) ? (a) : (b)

int wx[maxn],wy[maxn],c[maxn], h[maxn];
int sa[maxn], *rank, height[maxn];

int cmp(int *r,int a,int b,int l)
{
	return r[a] == r[b] && r[a+l] == r[b+l];	/* r[a] == r[b]就意味着a+l和b+l不会越界 */
}
/* 倍增法求后缀数组, 所有数组都从下标0开始 */
void da(char *r,int *sa,int n,int m)
{
	int 	i,l,p,*x=wx,*y=wy,*t;

	// 初始化x[i]，同时根据源字符串r得到第一轮的SA
	for(i = 0; i <= m; i++) c[i] = 0;
	for(i = 0; i < n; i++) c[x[i] = r[i]]++;

	for(i = 1; i <= m; i++) c[i] += c[i-1];
	for(i = n-1; i >= 0; i--) sa[--c[r[i]]] = i;

	//继续迭代，根据x计算SA
	for(l = 1,p = 1; p < n; l <<= 1, m = p)	/* p表示不同字符串的个数, p = n说明排序结束 */
	{
		// 根据上一次求出的sa，对第二关键字排序，结果保存在y[i]中, y[i] = j表示第i名的后缀是suffix[j]
		for(p = 0,i = n-l; i < n; i++) {				/* 第二关键字超出范围的后缀排在最前面 */
			y[p++] = i;
		}
		for(i = 0; i < n; i++) {
			if(sa[i] >= l) {
				y[p++] = sa[i]-l;
			}
		}

		//对第一关键字使用计数排序, 生成SA
		for(i = 0; i <= m; i++) c[i] = 0;
		for(i = 0; i < n; i++) c[x[y[i]]]++;
		for(i = 1; i <= m; i++) c[i] += c[i-1];
		for(i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];

		//根据SA生成rank，保存在数组x中，x[i] = j表示suffix[i]排在第j位, 相同的后缀名次相同，
		//所以还要根据上次的x数组来判断两个后缀是否一样，优化点：
		//交换x和y，这样y指向上次的x，原来y指向的空间用来存放新生成的rank
		for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++) {
			x[sa[i]] = cmp(y, sa[i-1], sa[i], l) ? p-1 : p++;
		}
	}
	rank = x;
}

int main()
{
	int		i, s, t, n, n1, max_len;

	char r[maxn], line[maxn];

	gets(r);
	n1 = strlen(r);
	gets(line);
	strcat(r, line);
	n = strlen(r)+1;	/* 一定要把末尾的\0也算进去 */

	max_len = -1;

	// 求后缀数组sa和排名数组wy
	da(r, sa, n, 156);

	// 求h[0]...h[n-1]
	for (i = 0; i < n; i++) {
		if (rank[i] == 1) h[i] = 0;
		else if (i == 0 || h[i-1] <= 1) {
			for (s = i, t = sa[rank[i]-1], h[i] = 0; r[s++] == r[t++]; h[i]++);
		}
		else {
			h[i] = h[i-1]-1;
			for (s = i+h[i], t = sa[rank[i]-1]+h[i]; r[s++] == r[t++]; h[i]++);
		}
	}
	//求height[1]...height[n]
	height[1] = 0;
	for (i = 2; i <= n; i++) {
		height[i] = h[sa[i]];
		// 后缀的最长前缀肯定出现在两个排名相邻的后缀之间，即height[i]的最大值
		// 而且两个后缀要属于不同的字符串
		if (((sa[i] < n1 && sa[i-1] >= n1) || (sa[i-1] < n1 && sa[i] >= n1)) && height[i] > max_len) {
			max_len = height[i];
		}
	}

	printf("%d\n", max_len);

	return 0;
}