洛谷 SP1811 LCS - Longest Common Substring 后缀数组

缘起

最长公共子串问题是著名的问题. 在【1】中使用DP给出了一种O(n^2)解法, 但显然这种解法不能处理1e5以上的字符串. 搓了 后缀数组的板子之后，来搞 洛谷 SP1811 LCS - Longest Common Substring

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入2 个长度不大于25w的字符串，输出这2 个字符串的最长公共子串的长度。如果没有公共子串则输出0 。

【输入】
仅仅两行，一行一个字符串

【输出】
LCS的长度

【样例输入】
alsdfkjfjkdsal
fdjskalajfkdsla

【样例输出】
3

【限制】
时间: 294ms, 空间: 1.46GB

其实【2】已经给出了后缀数组之 da+height的解法. 改一下maxn为 50w 就可以尝试提交了。

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 = 500005; // 直接修改一下maxn就行了
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)
{
	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);
		s[m] = '{';
		s[m+1] = 0;
		strcat(s,tt);
		da();
		height();
		int ans = 0;
		for (int i = 1; i< n; i++) 
		{
			if (ok(i))
			{
				ans = max(ans, lcp[i]);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

但是第一个点就被T掉了. 可见此题卡时间卡的真紧!

遂采用 dc3 + 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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
const int maxn = 500005;
char s[maxn], tt[maxn];
int n, mm, sa[maxn*3], r[maxn*3], wa[maxn*3], wb[maxn*3], wv[maxn*3], ws[maxn*3], lcp[maxn]; 

void sort(int *r, int *a, int *b, int n, int m)
{
	for (int i = 0;i<n; i++)
	{
		wv[i] = r[a[i]];
	}
	for (int i = 0;i<m;i++)
	{
		ws[i] = 0;
	}
	for (int i =0; i<n; i++)
	{
		ws[wv[i]]++;
	}
	for (int i = 1;i<m;i++)
	{
		ws[i]+=ws[i-1];
	}
	for (int i = n-1; ~i; i--)
	{
		b[--ws[wv[i]]]=a[i];
	} 
}

int c0(int *r, int a, int b)
{
	return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];
}

bool c12(int k, int *r, int a, int b)
{
	if (k==2) 
	{
		return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
	}
	else
	{
		return r[a]<r[b]||r[a]==r[b] && wv[a+1]<wv[b+1];
	}
}

void dc3(int *r, int *sa, int n, int m)
{
	int *rn = r+n, *san = sa+n, ta = 0, tb = (n+1)/3, tbc=0, p; 
	r[n] = r[n+1] =0;
	for (int i=0; i<n; i++)
	{
		if (i%3!=0)
		{
			wa[tbc++] = i;
		}
	} 
	sort(r+2, wa, wb, tbc, m); 
	sort(r+1, wb,wa, tbc, m);
	sort(r, wa,wb,tbc, m);
	rn[F(wb[0])]=0; p=1; 
	for (int i = 1; i<tbc; i++)
	{
		rn[F(wb[i])] = c0(r, wb[i-1], wb[i])?p-1:p++;
	}
	if (p<tbc)
	{ 
		dc3(rn, san, tbc, p); 
	} 
	else
	{
		for (int i =0 ; i<tbc; i++)
		{
			san[rn[i]] = i; 
		}
	}
	for (int i = 0; i<tbc; i++)
	{
		if (san[i]<tb)
		{
			wb[ta++] = san[i]*3;
		}
	}
	if (n%3==1) 
	{
		wb[ta++] = n-1;
	} 
	sort(r,wb,wa,ta,m);
	for (int i =0;i<tbc; i++)
	{
		wv[wb[i]=G(san[i])] = i;
	} 
	int i=0,j=0;
	for (p=0; i<ta && j<tbc; p++) 
	{
		sa[p] = c12(wb[j]%3, r, wa[i], wb[j])?wa[i++]:wb[j++]; 
	}
	while (i<ta)
	{
		sa[p++]=wa[i++];
	}
	while(j<tbc)
	{
		sa[p++]=wb[j++];
	}
}

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)
{
	return (sa[i]<mm)^(sa[i+1]<mm);
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%s%s", s,tt))
	{
		mm = strlen(s);
		s[mm] = '{';
		s[mm+1] = 0;
		strcat(s,tt);
		n = 0;
		while(s[n])
		{
			r[n]=s[n]-'a'+1;
			n++;
		}
		r[n] =0;
		dc3(r,sa,n+1,30); // 首先, 字符集的个数要扩充（因为引入了{）, 原先模板是27, 这里改成30
		for (int i = 1; i<=n; i++) // 其次, 和da+height不同的是, dc3+height并不会因为dc3完成之后, r中就是正确的(但是da+height的组合中da完毕之后,r中就是正确的),所以dc3完毕之后还要重置一波r才行
		{
			r[sa[i]] = i;
		}
		height();
		int ans = 0;
		for (int i = 1; i< n; i++) 
		{
			if (ok(i))
			{
				ans = max(ans, lcp[i]);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

ac情况

1
2
Accepted
80ms/21.00MB

参考

【1】https://yfsyfs.github.io/2019/10/06/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E4%B8%B2%E4%B9%8BDP%E8%A7%A3%E6%B3%95/

【2】https://yfsyfs.github.io/2019/10/11/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%95%B0%E7%BB%84/