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

时间：2022-05-14 05:16:35

题目链接：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;

}

　　

相关文章