hdu 1403 Longest Common Substring 最长公共子串 后缀树解法

缘起

【1】中讲解了最长公共子串的DP解法, 然鹅，这种解法在比赛中几乎没有什么卵用. ~ 遂 hdu 1403 Longest Common Substring

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
给你两个字符串，求他们的最长公共子串。

【输入】
多样例. 每个样例由2个不超过1w长度的字符串(仅由小写字母构成)构成. 

【输出】
对每个样例, 输出最长子串的长度

【样例输入】
banana
cianaic

【样例输出】
3

【限制】
4s 32MB

【2】中其实已经告诉我们该怎么做了——将 S1{S2| 作为字符串压入后缀树，找到最深（）的非叶节点，且该节点的叶节点既有 { 也有 |

所以我们基本上知道了, 后缀树的问题一般都是先ukk构建后缀树，然后在后缀树上dfs. 

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 maxn = 100005, SIZE = 28;
char s[maxn<<1], t[maxn];
int n,m, cnt,ans;

typedef struct SuffixTreeNode
{
	int s,e, len; // len是从根节点开始到当前节点为止的字符个数（包括当前节点的e-s个字符）
	SuffixTreeNode *next[SIZE], *parent, *link;
}SuffixTreeNode, *SuffixTree;

SuffixTree root;
SuffixTreeNode nodes[maxn<<2];

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

SuffixTree findnode(int j, int i, int &pos)
{
	if (j==i)
	{
		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;
}

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 dfs(SuffixTree cur) // 返回0、1、2分别表示当前节点仅有{结尾的叶子, 仅有|结尾的叶子, 两者都有
{
	if (cur->e==n+1) // 如果是叶子节点
	{
		return cur->len>m+1; // 如果长度>m+1, 则一定是 | 结尾的叶子, 即原s的后缀.
	}
	bool a = false,b = false; // 当前节点是否有{ 叶子, 当前节点是否有 |叶子
	for (int i = 0; i<SIZE; i++)
	{
		SuffixTree child = cur->next[i];
		if (child)
		{
			child->len = child->e-child->s+cur->len; // 统计孩子节点的len属性
			switch(dfs(child))
			{
			case 0:
				a = true;
				break;
			case 1:
				b = true;
				break;
			case 2:
				a = b = true;
				break; // 注意, 不能当a和b都是true的时候就break出for循环, 因为你还得dfs啊~
			}
		}
	}
	if (a&&b) // 汇总统计当前节点的情况
	{
		ans = max(ans, cur->len); // 优化ans
		return 2; // 两个都有
	}
	else if (b)
	{
		return 1; // 仅有|结尾的叶子
	}
	else
	{
		return 0; // 仅有 { 结尾的叶子
	}
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%s%s", s,t))
	{
		n = strlen(s),m = strlen(t);
		s[n] = '{',s[n+1]=0;
		t[m]='|', t[m+1]=0;
		strcat(s,t);
		n+=m+1;
		ukk();
		ans = 0;
		dfs(root);
		printf("%d\n", ans);
	}
	return 0;
}

ac情况

被无情的MLE掉了~（但是和网上的ac程序对拍过, 性能和正确性都没有问题） 这更坚定了我学习后缀数组的决心~

参考

【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://blog.csdn.net/f81892461/article/details/8643974