51nod 1088 1089 最长回文子串 后缀树

缘起

最长回文子串是亚马逊的面试题. 在【1】和【2】中分别使用了DP、马拉车两种解法. 虽然基本DP会T, 加上明显的暴力. 已经有三种解法了. 但是最长回文子串的正常解法还是后缀树和后缀数组（貌似后缀数组更加流行一点, 后缀树的缺点在【3】中已经吐槽过了） 但是本文想借 51nod 1088 最长回文子串 来练习一下后缀树. 以证明【3】中的后缀树的板子正确无误（【1】中的板子在 【4】的基础上精简了一些）.

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
输入一个字符串Str，输出Str里最长回文子串的长度。

回文串：指aba、abba、cccbccc、aaaa这种左右对称的字符串。

串的子串：一个串的子串指此（字符）串中连续的一部分字符构成的子（字符）串
例如 abc 这个串的子串：空串、a、b、c、ab、ac、bc、abc

输入
输入Str（对于1088，Str的长度 <= 1000，对于1089 Str长度 <= 100000)

输出
输出最长回文子串的长度L。

输入样例
daabaac

输出样例
5

限制
1s， 内存 131,072.0 KB

原本1089的初衷是想让我们使用马拉车，但是我马拉车在leetcode中用过了, 就是想刻意练习一下后缀树.

关于后缀树如何运用到求最长回文子串的问题中, 【5】中已经提及了. 这里再提及一下

首先，不得不提及的概念是广义后缀树(Generalized Suffix Tree GST) , 即【3】中处理的后缀树（即传统的后缀树）都是单个字符串的后缀形成的后缀树. 而广义后缀树存储任意多个单词的所有后缀。

得到广义后缀树的方法在《林厚从 · 高级数据结构》论述过. 有两种方法, 我采用了第一种——消耗空间比较大, 但是比较自然——就是将原字符串拼上’[‘, 再拼上另一个字符串（就本题而言, 是原字符串的逆序）再拼上一个新的不同于’A-Z’的 ‘\‘ , 即 S1[S2\ 这种, 对这个字符串建立后缀树. 然后只需要回答N对LCA询问即可. 而且这N对节点都是在叶子上（因为后缀对应的就是叶子节点嘛~）. 既然构建的字符串长度扩倍了，N也变成了2N+1

对单词的每一位置i(也就是从0到N-1)，获取LCA(S(i), S(N-i-1)), (这是为了奇回文) 以及LCA(S(i), S(N-i))(这是为了偶回文)。查找两次的原因是我们需要考虑奇数回文和偶数回文的情况。这步要考察每个i，所以复杂度是O(N)

找到最大的LCA这个节点，我们也就得到了回文的中心i以及回文的半径长度，自然也就得到了最长回文。所以总的复杂度O(N)。

所以我们的算法就很明显了.

  1. 建立广义后缀树（虽说是广义, 但其实就是2个字符串），建立的算法是先建立一个字符串的, 再读入另一个字符串的. 哎呀, 搞那么复杂干啥, 不就是读入2拨儿后缀嘛~ 一拨儿后缀以 \$ 结尾, 一拨儿后缀以 # 结尾.
  2. 采用tarjan算法解决步骤1中构建的广义后缀树上的LCA问题. 因为我们是知道要求哪些节点的LCA的. 所以采用tarjan这种离线算法比较好（写起来简单, 而且速度快）关于LCA的tarjan算法参见【6】
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
//#include "stdafx.h"
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int SIZE = 28, maxn = 100005;
char s[maxn<<1];
int n, cnt,f[maxn<<2], d[maxn<<1],ans=1; // d[i]记录了第s[i,...]这个后缀它对应的nodes数组的索引
typedef struct SuffixTreeNode
{
	int s,e, len, index; // len是从根节点到当前节点总共包含的字符数量(包括当前节点的字符在内), 这个数量的意义对于叶子而言就是唯一识别它到底代表哪个后缀, index是该节点在nodes数组中的编号
	SuffixTreeNode *next[SIZE], *parent, *link;
}SuffixTreeNode, *SuffixTree;

SuffixTreeNode nodes[maxn<<2];

SuffixTree root;

SuffixTree findnode(int j, int i, int &pos)
{
	if (i==j)
	{
		pos = 0;
		return root;
	}
	SuffixTree p = root->next[s[j]-'A'];
	pos = p->s;
	while(p->e-p->s<i-j)
	{
		j+=p->e-p->s;
		p = p->next[s[j]-'A'];
		pos = p->s;
	}
	pos+=i-j;
	return p;
}

SuffixTree newnode(int s, int e, SuffixTree parent)
{
	SuffixTree p = &nodes[cnt];
	p->s = s, p->e = e, p->parent = parent, p->link = 0, p->len = 0, p->index = cnt;
	memset(p->next, 0, sizeof(p->next));
	cnt++;
	return p;
}

void ukk()
{
	cnt =0;
	root = newnode(0,0,0);
	SuffixTree cur = root;
	for (int i = 0, m = 0, pos = 0; i<=n; i++)
	{
		SuffixTree last =0;
		for (int j=m; j<=i; j++)
		{
			if (last)
			{
				if (cur->link)
				{
					cur = cur->link;
					pos = cur->e;
				}
				else
				{
					cur = findnode(j,i,pos);
				}
			}
			if (pos<cur->e)
			{
				if (s[i]==s[pos])
				{
					pos++;
					break;
				}
				else
				{
					SuffixTree inter = newnode(cur->s, pos, cur->parent);
					cur->parent->next[s[cur->s]-'A'] = inter;
					cur->s = pos;
					cur->parent = inter;
					inter->next[s[i]-'A'] = newnode(i,n+1,inter);
					inter->next[s[pos]-'A'] = cur;
					cur = inter;
				}
			}
			else
			{
				if (cur->next[s[i]-'A'])
				{
					cur = cur->next[s[i]-'A'];
					pos = cur->s+1;
					break;
				}
				else
				{
					cur->next[s[i]-'A'] = newnode(i,n+1,cur);
				}
			}
			if (last)
			{
				last->link = cur;
			}
			last = cur;
			m++;
		}
	}
}

int getf(int i)
{
	return i==f[i]?i:f[i] = getf(f[i]);
}

void dfs(SuffixTree cur)
{
	for (int i=  0; i<SIZE; i++)
	{
		SuffixTree child = cur->next[i];
		if (child)
		{
			child->len = child->e-child->s+cur->len;
			dfs(child);
			f[child->index] = cur->index;
		}
	}
	if (cur->e==n+1) // 如果搜完的这个节点是叶子节点的话
	{
		int t = n+1-cur->len; // cur这个叶子对应 s[t,...]这个后缀,前面说了,len属性可以知道它到底是哪个后缀
		d[t] = cur->index; // s[t,...]这个后缀对应的叶子节点就是nodes[cur->index]
		if (t && t<n-1 && ~d[n-1-t] && s[t]!='[' && s[n-1-t]!='[') // 考察奇回文 ~d[n-1-t] 说明 s[n-1-t,...] 这个后缀对应的叶子节点已经搜过了,注意t的范围, 不能仅仅考察t<n/2, 因为你不晓得到底是逆串后缀先搜到还是原串后缀先搜到
		{
			int k = getf(d[n-1-t]);
			int kk = nodes[k].len;
			ans = max(ans, (kk<<1)-1); // len属性其实是回文半径
		}
		if (t && t<n && ~d[n-t] && s[t]!='[' && s[n-t]!='[') // 考察偶回文,~d[n-t] 说明 s[n-t,...] 这个后缀对应的叶子节点已经搜过了
		{
			int k = getf(d[n-t]);
			int kk = nodes[k].len;
			ans = max(ans, nodes[getf(d[n-t])].len<<1);
		}
	}
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%s", s);
	n = strlen(s);
	s[n] = '[';
	for (int i = n+1;i<=2*n;i++)
	{
		s[i] = s[2*n-i];
	}
	s[2*n+1] = '\\';
	s[2*n+2] = 0;
	n = 2*n+1;
	ukk();
	for (int i = 0; i<cnt; i++)
	{
		f[i] = i;
	}
	memset(d, -1, sizeof(d));
	dfs(root); // 跑tarjan算法解决LCA问题
	printf("%d", ans);
	return 0;
}

ac情况

1088

1
2
3
yfs
2019/10/7 9:22:02 C++ 15ms
3,384KB Accepted

1089 总共20个数据点, 19个过了. 1个点被T掉了. 这个点的数据我花钱下下来了，大概的样子就是

1
AAA...AAABBBBBBBBBBBBBBBAAA.....AAA

省略号表示成吨的A，反正字符串总长99999.

跑了一遍, 输出结果是正确的. 所以就是超时导致的T，而不是死循环.

不知道为什么会超时, 我对于上面的代码做了测试, 对于上述测试数据, 只需要统计一下ukk最内层的for循环走了几次即可. 结果发现走的次数一直恒为字符串长度的2倍, 由此可知, ukk算法的确是O(n)的. 但是不知道为什么依旧被T，51nod真的是蜜汁服务器啊~

1
2
3
yfs
2019/10/7 9:25:52 C++ 1015ms
104,236KB Time Limit Exceed

值得注意的是内存的耗费达到了惊人的 100+MB。所以后缀树是相当耗费内存的.

所以比赛的时候很少有人会去写后缀树. 因为相比其他SA、SAM、KMP代码复杂不说，而且就算辛辛苦苦准确无误的搓出来了，被MLE的可能性相当高.

参考

【1】https://yfsyfs.github.io/2019/10/06/%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2%E4%B9%8BDP%E5%81%9A%E6%B3%95/

【2】

https://yfsyfs.github.io/2019/07/08/Manacher%E7%AE%97%E6%B3%95-leetcode-5-%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2/

【3】https://yfsyfs.github.io/2019/10/06/poj-3461-Oulipo-%E5%90%8E%E7%BC%80%E6%A0%91-KMP/

【4】https://yfsyfs.github.io/2019/08/03/hdu-3518-Boring-counting-%E5%90%8E%E7%BC%80%E6%A0%91/

【5】https://blog.csdn.net/f81892461/article/details/8643974

【6】https://yfsyfs.github.io/2019/07/18/hdu-2586-How-far-away-LCA-Tarjan解法/