hdu 1403 Longest Common Substring 最长公共子串 后缀数组

缘起

【1】中求LCS的后缀树解法被无情的MLE掉了. 所以我打算学习了后缀数组用后缀树完成对他的一击.

分析

题目见【1】好了.

这里说一下思路. 其实和 【2】十分的相似. 只需要使用S和T中间用一个没有在他们中间出现过的字符, 例如{, 然后建立S{T 的后缀数组. 注意, 因为长度在10w以内, 所以 ‘S{T’ 拼起来长度不会超过20w. da+height足以了. 不需要dc3

然后求出这个新的字符串的lcp数组. 然后lcp的最大值就是LCS的长度? 非也非也, 必须要这相邻的两个后缀不属于同一个字符串（S或者T）才行. 而这使用sa、r很好判断. 算法的复杂度能达到 O(nlogn), n=|S|+|T|, 如果采用dc3的话, 可以到达 O(|S|+|T|) 更加的优秀. 但是本题不需要。 da+height能过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

const int maxn = 200005;
char s[maxn], tt[maxn];
int n,m,k,sa[maxn],r[maxn],t[maxn],lcp[maxn];

bool c0(int i,int j)
{
	if (r[i]!=r[j])
	{
		return r[i]<r[j];
	}
	int ri = i+k<=n?r[i+k]:-1, rj = j+k<=n?r[j+k]:-1;
	return ri<rj;
}

void da()
{
	n = strlen(s);
	k = 1;
	for (int i = 0;i<n; i++)
	{
		sa[i] = i;
		r[i] = s[i]-'a'+1;
	}
	r[n]= 0, sa[n] = n;
	while(k<=n)
	{
		sort(sa,sa+n+1,c0);
		t[sa[0]] = 0;
		for (int i = 1;i<=n; i++)
		{
			t[sa[i]] = t[sa[i-1]]+c0(sa[i-1], sa[i]);
		}
		memcpy(r,t,(n+1)*sizeof(int));
		k<<=1;
	}
}

void height()
{
	int h = 0;
	for (int i = 0,j; i<n; i++)
	{
		if (r[i]==1)
		{
			continue;
		}
		j = sa[r[i]-1];
		if (h)
		{
			h--;
		}
		while(i+h<n && j+h<n)
		{
			if (s[i+h]!=s[j+h])
			{
				break;
			}
			h++;
		}
		lcp[r[i]-1] = h;
	}
}

bool ok(int i) // 判断 sa[i]和sa[i+1]是不是同一个字符串中的, false表示是, true表示不是
{
	return (sa[i]<m)^(sa[i+1]<m);
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%s%s", s,tt))
	{
		m = strlen(s); // m备份一下s的长度
		s[m] = '{';
		s[m+1] = 0;
		strcat(s,tt);
		da();
		height();
		int ans = 0;
		for (int i = 1; i< n; i++) // lcp[i]是S[sa[i],...]和S[sa[i+1],...]的LCP
		{
			if (ok(i))
			{
				ans = max(ans, lcp[i]);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

ac情况

Status Accepted
Time 904ms
Memory 4632kB
Length 1426
Lang G++
Submitted 2019-10-11 18:22:48
Shared
RemoteRunId 30864792

参考

【1】https://yfsyfs.github.io/2019/10/07/hdu-1403-Longest-Common-Substring-%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E4%B8%B2-%E5%90%8E%E7%BC%80%E6%A0%91%E8%A7%A3%E6%B3%95/

【2】https://yfsyfs.github.io/2019/10/11/51nod-1089-%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2-V2-%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84/