leetcode 1044 最长重复子串 后缀树

缘起

继续研究后缀树的运用. 来到了最后一个运用, 再后面就要上后缀数组了. leetcode 1044 最长重复子串

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。

返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 ""。）

示例 1：

输入："banana"
输出："ana"
示例 2：

输入："abcd"
输出：""
 

提示：

1. 2 <= S.length <= 10^5
2. S 由小写英文字母组成。

关于此题的主流解法有如下两种

  1. 二分答案+哈希. 类似于 rabin-karp的思想. 这个思路是最显然的. 就是将a~z视作是26进制数. 然后用洪特规则.当然鉴于字符串长度可能到达1e5, 所以二分是必须的. 但是感觉吃相比较难看. 不想这样写. 反正不难.
  2. 主流解法——后缀数组. 即SA， 但是目前不会, 马上就会.
  3. 本文介绍的后缀树解法.

后缀树解决最长重复子串问题的做法其实在【1】中已经论述过了.

就是ukk构造S的后缀树. 然后找到最深的非叶子节点即可. 这个深是指从root开始所经历过的字符个数（包括当前节点的字符），最深非叶节点所经历的字符串起来就是最长重复子串的长度。

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
class Solution {
public:
	string longestDupSubstring(string S) {
		s = S;
		n = S.length();
		s.push_back('{');
		ans = 0, start = -1;
		ukk();
		dfs(root);
		return ans?S.substr(start, ans):"";
	}

private:
	typedef struct SuffixTreeNode
	{
		int s,e,len; // len是从root到当前节点的最长
		SuffixTreeNode *next[27], *parent, *link;
	}SuffixTreeNode, *SuffixTree;
	
	SuffixTree root;
	SuffixTreeNode nodes[100005<<1];
	string s;
	int cnt,n, ans,start; // ans是最长重复子串的长度, start表示该最长重复子串为 s[start,....]
	
	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;
		memset(p->next, 0, sizeof(p->next));
		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++;
			}
		}
	}

	void dfs(SuffixTree cur)
	{
		if (cur->e==n+1) // 叶子节点直接返回
		{
			return;
		}
		for (int i = 0; i<27; i++)
		{
			SuffixTree child = cur->next[i];
			if (child)
			{
				child->len = child->e-child->s+cur->len;
				dfs(child);
			}
		}
		if (ans<cur->len) // 对非叶子节点维护答案, cur->e-ans就知道start了
		{
			ans = cur->len;
			start = cur->e - ans;
		}
	}
};

执行结果：

1
2
3
4
5
6
7
通过

显示详情

执行用时 :256 ms, 在所有 C++ 提交中击败了90.28%的用户

内存消耗 :66.6 MB, 在所有 C++ 提交中击败了100.00%的用户

parden? 竟然消耗内存最少? 卧槽~ SA的C艹玩家死光了吗?

本题其实使用 SA 来切也是很简单的——思想在罗大神09年IOI论文P18 讲清楚了. 答案就是lcp数组中的最大值. 复杂度是On的.

参考

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