poj 2774 Long Long Message 后缀数组

//	poj 2774 Long Long Message 后缀数组
//
//	题目大意:
//	
//		求两个串的最长公共子串.
//
//	解题思路:
//
//		后缀数组.将两个字符串用一个不出现在两个字符串的其他字符连接,并在最后
//	同样用一个字符作为结束.一个串的子串,一定是某个后缀的前缀.求出height数组
//	height[i]表示sa[i-1]和sa[i]的公共前缀LCP.这样将两个字符串接起来.最长公共
//	子串一定会是相邻的.如果不相邻,那肯定会有拥有与他更长的公共串的串与其相邻
//	因为他们是排在一起的.这一点是关键.最后只要求是否在两个不相同的串中取出一个
//	最大的height[i]就是所谓的答案.
//
//	感悟:
//
//		尽管看到了罗前辈的论文,知道整体的思想,学习了刘老师的倍增算法.按照自己的理解
//	敲了一下后缀数组,结果一直是RE,一直是WA,搜了搜题解.发现各位前辈大牛写的都是差不多
//	的.但是自己就是一直在wa.然后发现,自己并没有懂得后缀数组.不知道要在后面加上一个最小
//	的字符.(这是为了方便比较大小)我的理解就是这个字符定义下了一个标杆,由于比所有的都要小
//	更加有效的实现了倍增.两个关键字的排序结合了一个小的标号,不仅不影响结果,反而会更加有效
//	实现两两比较.这是我WA的第一个原因.第二个就是擅自将c的范围改到了500,变小了.其实这样是
//	有问题的.因为按照的是基数排序.最后的结果肯定是0~n-1范围的.所以c小了,肯定是会RE的.这是
//	所谓的基数排序.又一次加强了自己的理解.这道题从开始看,到最后的AC和理解.一共用了5个小时
//	期间,我一直各种debug.怀疑这里错了,怀疑那里错了.现在还是脑子一团浆糊.到不了真正能够应用的
//	层面,但我依然会坚持.没有人教,那么有的就是自学.有的是自己的脑子.在最困难,最焦虑的时候.冷静
//	清醒.千万不能慌,虽然这是一道后缀数组的裸题.但我在了解了做法的基础上,依然是花了5个小时才
//	AC.还是自己太笨了,也是倍增太神奇了.套模板,我还是永远不会.只能一遍一遍的理解.
//		总的来说,人生第一道后缀数组,虽然艰辛无数.但还是有那么一丝的收获.哪怕只是一点点,我也会
//	为之头破血流.更何况,才费点脑子的事儿,继续加油吧!FIGHTING!!!

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

using namespace std;

const int MAX_N = 500009;
int n;

int c[MAX_N];
int sa[MAX_N];
int height[MAX_N];
int rank[MAX_N];
int t[MAX_N];
int t2[MAX_N];

char str1[MAX_N];
char str2[MAX_N];
int u;
int s[MAX_N];
void build_sa(int n,int m){
	int *x = t;
	int *y = t2;
	for (int i=0;i<m;i++)	c[i] = 0;
	for (int i=0;i<n;i++)	c[x[i] = s[i]]++;
	for (int i=1;i<m;i++)	c[i] += c[i-1];
	for (int i=n-1;i>=0;i--)	sa[--c[x[i]]] = i;

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

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

		swap(x,y);
		p = 1;
		x[sa[0]] = 0;
		for (int i=1;i<n;i++)
			x[sa[i]] = y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k] == y[sa[i]+k]?p-1:p++;

		if (p>=n)
			break;
		m = p;
	}
}

void get_h(int n){
	for (int i = 0;i < n;i++)
		rank[sa[i]] = i;
	int k = 0;
	//int j;
	//height[0] = 0;
	for (int i = 0;i < n;i++){
		if (k) k--;
		int j = sa[rank[i]-1];
		while(s[i+k]==s[j+k])
			k++;
		height[rank[i]] = k;
		//cout << k << endl;
	}
}

bool judge(int i){
	if ((sa[i-1]<u && u < sa[i]) ||(sa[i] < u && u < sa[i-1]))
		return true;
	return false;
}

void print(int *a){
	for (int i=0;i<n;i++){
		printf("%d ",a[i]);
	}
	cout << endl;
}

int get_long(){
	int mx = 0;
	for (int i=1;i<n;i++){
		if (height[i]>mx && judge(i)){
			mx = height[i];
		}
	}
	return mx;
}

void solve(){
	int len1 = strlen(str1);
	int len2 = strlen(str2);
	u = len1;
	//str1[len++] = '#';
//	for (int i = 0;str2[i];i++,len++){
//		str1[len] = str2[i];
//	}
//	str1[len++] = 0;
//	n = len;

	n = 0;
	
	for (int i=0;str1[i];i++)
		s[n++] = str1[i] - 'a' + 1;
	
	s[n++] = 28;
	for (int i =0;str2[i];i++)
		s[n++] = str2[i] - 'a' + 1;

	//cout << n << " " << len1 + len2 << endl;
	s[n++] = 0;
	build_sa(n,30);

	//print(sa);
	//cout << str1 << endl;
	get_h(n);
	//print(height);
	printf("%d\n",get_long());
}

int main(){
	//freopen("1.txt","r",stdin);
	while(scanf("%s%s",str1,str2)!=EOF){
		solve();
	}
	return 0;
}

poj 2774 Long Long Message 后缀数组

原文：http://blog.csdn.net/timelimite/article/details/47399501