首页 > 代码库 > [POJ 2774] Long Long Message 【后缀数组】

[POJ 2774] Long Long Message 【后缀数组】

2024-10-31 03:06:40   205人阅读

题目链接：POJ - 2774

 

题目分析

题目要求求出两个字符串的最长公共子串，使用后缀数组求解会十分容易。

将两个字符串用特殊字符隔开再连接到一起，求出后缀数组。

可以看出，最长公共子串就是两个字符串分别的一个后缀的 LCP ，并且这两个后缀在 SA 中一定是相邻的。

那么他们的 LCP 就是 Height[i] ，当然，Height[i] 的最大值不一定就是 LCS ，因为可能 SA[i] 和 SA[i-1] 是在同一个字符串中。

那么判断一下，如果 SA[i] 与 SA[i - 1] 分别在两个字符串中，就用 Height[i] 更新 Ans 。

 

代码

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int MaxL = 200000 + 15;int n, l1, l2, Ans;int A[MaxL], Rank[MaxL], Height[MaxL], SA[MaxL];int VA[MaxL], VB[MaxL], VC[MaxL], Sum[MaxL];char S1[MaxL], S2[MaxL];inline bool Cmp(int *a, int x, int y, int l) {	return (a[x] == a[y]) && (a[x + l] == a[y + l]);}void DA(int *A, int n, int m) {	int *x, *y, *t;	x = VA; y = VB;	for (int i = 1; i <= m; ++i) Sum[i] = 0;	for (int i = 1; i <= n; ++i) ++Sum[x[i] = A[i]];	for (int i = 2; i <= m; ++i) Sum[i] += Sum[i - 1];	for (int i = n; i >= 1; --i) SA[Sum[x[i]]--] = i;	int p, q;	p = 0;	for (int j = 1; p < n; j <<= 1, m = p) {		q = 0;		for (int i = n - j + 1; i <= n; ++i) y[++q] = i;		for (int i = 1; i <= n; ++i) {			if (SA[i] <= j) continue;			y[++q] = SA[i] - j;		}		for (int i = 1; i <= n; ++i) VC[i] = x[y[i]];		for (int i = 1; i <= m; ++i) Sum[i] = 0;		for (int i = 1; i <= n; ++i) ++Sum[VC[i]];		for (int i = 2; i <= m; ++i) Sum[i] += Sum[i - 1];		for (int i = n; i >= 1; --i) SA[Sum[VC[i]]--] = y[i];		t = x; x = y; y = t;		x[SA[1]] = 1; p = 1;		for (int i = 2; i <= n; ++i) 			x[SA[i]] = Cmp(y, SA[i], SA[i - 1], j) ? p : ++p;	}	for (int i = 1; i <= n; ++i) Rank[SA[i]] = i;		//GetHeight	int h, o;	h = 0;	for (int i = 1; i <= n; ++i) {		if (Rank[i] == 1) continue;		o = SA[Rank[i] - 1];		while (A[i + h] == A[o + h]) ++h;		Height[Rank[i]] = h;		if (h > 0) --h;	} }int main() {	scanf("%s%s", S1 + 1, S2 + 1);	l1 = strlen(S1 + 1);	l2 = strlen(S2 + 1);	for (int i = 1; i <= l1; ++i) 		A[i] = S1[i] - ‘a‘ + 1;	A[l1 + 1] = 27;	for (int i = 1; i <= l2; ++i) 		A[l1 + 1 + i] = S2[i] - ‘a‘ + 1;	A[l1 + 1 + l2 + 1] = 28;	n = l1 + 1 + l2 + 1;		DA(A, n, 28);		Ans = 0;	for (int i = 2; i <= n - 1; ++i) {		if (Height[i] > Ans) {			if (SA[i] <= l1 && SA[i - 1] > l1 + 1) Ans = Height[i];			if (SA[i] > l1 + 1 && SA[i - 1] <= l1) Ans = Height[i];		}	}	printf("%d\n", Ans);	return 0;}

　　

[POJ 2774] Long Long Message 【后缀数组】


联系
我们