学步园

题目链接：http://poj.org/problem?id=2774

题目大意：给定两个字符串，求最长的公共子串，和DP里的LCS(最长公共子序列）问题完全不一样

解题思路：本题可用后缀数组解决，将两个串拼接，中间用和末尾都用一个很小很小的字符隔开，然后求各个后缀的rank以及每个后缀与其他后缀的最长公共前缀height数组，height数组中符合条件的最大值就是答案。最后在更新答案的时候判断有最长公共前缀的两个后缀是不是属于分别属于两个字符串，如果是，那就更新。

        今天在看后缀数组，知道大概的思想，但是具体的实现看的是云里雾里。试着表达下自己的理解，后缀数组就是将某串的后缀按字典序排序存储在数组中，后缀数组sa，sa[i]的意思是排名为i的后缀是谁，rank数组,rank[i]的意思是第i个后缀排名多少。有倍增算法和DC3算法构造后缀后组，本文采取的是倍增算法，用的是《后缀数组--字符串处理的有力工具》里的模板，这篇论文出于Noi高中生之手，我一个大学生深感压力。关于倍增算法大家还是去膜拜那篇论文吧，百度搜索下一坨。在本题中还用到height，储存的是每个后缀与其他后缀最长的公共前缀。

测试数据：

abbbccc

bcc

iloveyoubutfuckyou

butfuck

whenyouseemeyouloveme

hahachoumei

代码：

#include <stdio.h>
#include <string.h>
#define MAX 500000
#define max(a,b) (a) > (b) ? (a) : (b)


int arr[MAX],wa[MAX],wb[MAX];
int wv[MAX],wn[MAX];
int rank[MAX],sa[MAX],h[MAX];


int cmp(int *r,int a,int b,int l)
{ 
	return r[a] == r[b] && r[a+l] == r[b+l]; 
}
void Double(int *r,int n,int m) 
{
	int i,j,k,p;		   //p 不同字符串个数
	int *x = wa,*y = wb,*t;//rank值保存在x中

	//对r中长度为1的子串进行基数排序
	for (i = 0; i < m; ++i) wn[i] = 0;
	for (i = 0; i < n; ++i) wn[x[i]=r[i]]++;
	for (i = 1; i < m; ++i) wn[i] += wn[i-1];
	for (i = n - 1; i >= 0; --i) sa[--wn[x[i]]] = i;

	//对r中长度为j的子串进行基数排序
	for (j = 1,p = 1; p < n; j *= 2,m = p) 
	{
		for (p = 0,i = n - j; 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) wn[i] = 0;
		for (i = 0; i < n; ++i) wn[wv[i]]++;
		for (i = 1; i < m; ++i) wn[i] += wn[i-1];
		for (i = n - 1; i >= 0; --i) sa[--wn[wv[i]]] = y[i];


		t = x,x = y,y = t,p = 1;
		for (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 n) 
{
	int i,j,k = 0;
	for (i = 1; i <= n; ++i) rank[sa[i]] = i;	//sa转化为rank
	for (i = 0; i < n; h[rank[i++]] = k)
		for (k ? k--:0,j = sa[rank[i]-1]; r[i+k] == r[j+k]; k++);
}


int main()
{
	int i,j,k,t;
	int ans,n1,n2,n3;
	char s1[MAX],s2[MAX];


	while (scanf("%s%s",s1,s2) != EOF) 
	{	
		n1 = strlen(s1),n2 = strlen(s2);
		n3 = n1 + n2 + 1;
		for (i = 0; i < n1; ++i) arr[i] = (int)s1[i]; //将两个字符串拼接起来
		arr[n1] = 0;
		for (i = 0; i < n2; ++i) arr[n1+1+i] = (int)s2[i];
		arr[n1+1+n2+1] = 0;


		Double(arr,n3+1,256);			//求后缀数组
		Calheight(arr,n3);			//求height数组（即最长公共前缀）


		ans = 0;
		for (i = 1; i <= n3; ++i)
			if (sa[i] < n1 && sa[i-1] > n1 || sa[i] > n1 && sa[i-1] < n1)
				ans = max(ans,h[i]);
		printf("%d\n",ans);
	}
}


本文ZeroClock原创，但可以转载，因为我们是兄弟。