POJ 2774 Long Long Message(后缀数组)

/*
题意：输出两个字符串最大公共子串

题解：将两个字符串对接，中间使用一个从未出现过的字符相连，然后问题就可以使用后缀数组解决
*/

#include <iostream>
using namespace std;
const int nMax = 1000000;
const int mMax = 0x7fff;
char str[nMax];
int num[nMax];
int wa[nMax], wb[nMax];
int _ws[mMax], wv[nMax];
int rank[nMax], sa[nMax];
int height[nMax];

bool cmp(int *r, int a, int b, int l)
{
	return r[a] == r[b] && r[a + l] == r[b + l];
}

void da(int *r, int *sa, int n, int m)
{
	int i, j, p;
	int *x = wa, *y = wb, *t;
	for(i = 0; i < m; ++ i) _ws[i] = 0;
	for(i = 0; i < n; ++ i) _ws[x[i] = r[i]] ++;
	for(i = 1; i < m; ++ i) _ws[i] += _ws[i - 1];
	for(i = n - 1; i >= 0; -- i) sa[--_ws[x[i]]] = i;

	for(j = 1, p = 1; p < n; j <<= 1, m = p)
	{
		for(i = n - j, p = 0; i < n; ++ i) y[p ++] = i;
		for(i = 0; i < n; ++ i)
			if(sa[i] >= j)
				y[p ++] = sa[i] - j;

		for(i = 0; i < n; ++ i) wv[i] = x[y[i]];
		for(i = 0; i < m; ++ i) _ws[i] = 0;
		for(i = 0; i < n; ++ i) _ws[wv[i]] ++;
		for(i = 1; i < m; ++ i) _ws[i] += _ws[i - 1];
		for(i = n - 1; i >= 0; -- i) sa[-- _ws[wv[i]]] = y[i];

		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], j) ? p - 1: p ++;
	}
}

void calHeight(int *r, int *sa, int n)
{
	int i, j, k = 0;
	for(i = 1; i <= n; ++ i) rank[sa[i]] = i;
	for(i = 0; i < n; height[rank[i ++]] = k)
		for(k ? k -- : 0, j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k ++);
}

int main()
{
	//freopen("e://data.txt", "r", stdin);
	while(scanf("%s", str) != EOF)
	{
		int len1 = strlen(str);
		int n = 0;
		for(int i = 0; i < len1; ++ i)
			num[n ++] = str[i];
		num[n ++] = '#';
		scanf("%s", str);
		int len2 = strlen(str);
		for(int i = 0; i <= len2; ++ i)
			num[n ++] = str[i];
		da(num, sa, n, mMax + 1);
		calHeight(num, sa, n - 1);
		int ans = 0;
		for(int i = 1; i < n; ++ i)
		{
			if((sa[i] < len1 && sa[i - 1] > len1) || (sa[i] > len1 && sa[i - 1] < len1))
				ans = max(ans, height[i]);
		}
		printf("%d\n", ans);
	}
	return 0;
}