51nod 1089 最长回文子串 V2 后缀数组

缘起

本想在【2】中一口气验证【3】中搓的da、dc3两块板子，但是class中自定义sort又不会写~ 只好作罢~ 【2】中仅仅证明了【3】中的dc3的板子是正确无误的. 下面又拿起了【1】中的题目——求最长重复出现子串（允许重叠）。【1】中已经用后缀树切了它（但是被T掉了），现在再用后缀数组来切它一次.

分析

题目见【1】. 这里先讲思路.

将整个字符串反过来写在原字符串后面， 中间用一个特殊的字符（如\$）隔开。 这样就把问题变为了求这个新的字符串的某两个后缀（这两个后缀的索引是有关系的）的LCP. 然后用【3】中最后讲解的如何将求任意两个后缀的LCP转换为RMQ问题即可.

情况1是奇回文, 情况2是偶回文.

因为本题的数据规模是1e5, 所以使用da+height没问题.

至于lcp[1,…,n-1]上的RMQ问题，因为lcp[i]=S[sa[i],…]和S[sa[i+1],…]之间的LCP（1<=i<n）. 而我们知道要计算哪些后缀之间的LCP，所以宜采用RMQ的ST表算法（参见【4】）。

假设n（原串s的长度）已经变成2n+1,m保存了原先的n, S是按照上面的办法扩展的字符串

对于奇回文，我们要检查的是 S[i,…]和S[n-1-i,…] 这两个后缀的LCP. 0<i<m-1

对于偶回文, 我们要检查的是 S[i,…] 和 S[n-i,…] 这两个后缀的LCP. 0<i<m

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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

const int maxn = 2e5+5;
char s[maxn];
int n, m, k, lcp[maxn],sa[maxn], r[maxn], t[maxn], st[20][maxn]; // st表, 最多20层(20w的以2为底的对数)

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()
{
	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;
	}
}

void build() // 构建 lcp[1,...,n-1]的st表
{
	memcpy(st[0]+1, lcp+1, sizeof(lcp));
	int k = 1;
	while(1<<k<n)
	{
		for (int i = 1; i<n; i++)
		{
			st[k][i] = st[k-1][i];
			if (i+(1<<k-1)<n)
			{
				st[k][i] = min(st[k][i], st[k-1][i+(1<<k-1)]);
			}
		}
		k++;
	}
}

int rmq(int i, int j) // 计算 lcp[i,..,j]的rmq
{
	int k = 0;
	while((1<<k)<=(j-i+1))
	{
		k++;
	} // 最后定位在第k-1层定胜负
	return min(st[k-1][i], st[k-1][j-(1<<k-1)+1]);
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%s", s);
	m = n = strlen(s); // m的作用是备份n
	s[n] = '[';
	for (int i = n+1; ~(2*n-i); i++)
	{
		s[i] = s[2*n-i];
	}
	n = 2*n+1;
	da();
	height(); // 结果 lcp[1,...,n-1]中,lcp[i]表示S[sa[i],...]和S[sa[i+1],...]之间的LCP
	build(); // 构建st表
	int ans = 1, left, right;
	for (int i = 1;i<m-1;i++)
	{
		left = r[i], right = r[n-1-i];
		if (left>right)
		{
			swap(left, right);
		}
		ans = max(ans, (rmq(left, right-1)<<1)-1); // rmq求出的仅仅是回文半径
	} // 检查奇回文
	for (int i = 1; i<m;i++)
	{
		left = r[i], right = r[n-i];
		if (left>right)
		{
			swap(left, right);
		}
		ans = max(ans, rmq(left, right-1)<<1);
	}// 检查偶回文
	printf("%d\n", ans);
	return 0;
}

ac情况

1
2
3
yfs
2019/10/11 17:08:14C++ 343ms
19,088KB Accepted

对比 【1】中的 100MB 的内存耗费, 真心牛逼啊~

参考

【1】https://yfsyfs.github.io/2019/10/07/51nod-1088-1089-%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2-%E5%90%8E%E7%BC%80%E6%A0%91/

【2】https://yfsyfs.github.io/2019/10/10/leetcode-28-%E5%AE%9E%E7%8E%B0-strStr-%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84/

【3】https://yfsyfs.github.io/2019/10/07/%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84%E5%AD%A6%E4%B9%A0/

【4】https://yfsyfs.github.io/2019/07/15/RMQ/