★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★➤微信公众号：山青咏芝（shanqingyongzhi）➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）➤GitHub地址：https://github.com/strengthen/LeetCode➤原文地址：https://www.cnblogs.com/strengthen/p/10852170.html ➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
Given a string S, consider all duplicated substrings: (contiguous) substrings of S that occur 2 or more times. (The occurrences may overlap.)
Return any duplicated substring that has the longest possible length. (If S does not have a duplicated substring, the answer is "".)
Example 1:
Input:
"banana"
Output: "ana"
Example 2:
Input:
"abcd"
Output: ""
Note:
2 <= S.length <= 10^5S consists of lowercase English letters.
给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。
返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 ""。）
示例 1：
输入："banana"
输出："ana"
示例 2：
输入："abcd"
输出：""
提示：
2 <= S.length <= 10^5S 由小写英文字母组成。
Runtime: 356 ms
Memory Usage: 27.3 MB
1 class Solution {
2 func longestDupSubstring(_ S: String) ->
String {
3 var sa:[Int] = suffixArray(Array(S),
26)
4 let n:Int =
S.count
5 var lcp:[Int] =
buildLCP(Array(S), sa)
6 var isa:[Int] = [Int](repeating:
0,count:n)
7 for i
in 0..<n {isa[sa[i]] =
i}
8 var max:Int =
0
9 var arg:Int = -
1
10 for i
in 1..<
n
11 {
12 if lcp[i] >
max
13 {
14 max =
lcp[i]
15 arg =
i
16 }
17 }
18 if arg == -
1 {
return String()}
19 return S.subString(sa[arg], max +
1)
20 }
21
22 func buildLCP(_ str:[Character],_ sa:[Int]) ->
[Int]
23 {
24 let n:Int =
str.count
25 var h:Int =
0
26 var lcp:[Int] = [Int](repeating:
0,count:n)
27 var isa:[Int] = [Int](repeating:
0,count:n)
28 for i
in 0..<n {isa[sa[i]] =
i}
29 for i
in 0..<
n
30 {
31 if isa[i] >
0
32 {
33 let j:Int = sa[isa[i] -
1]
34 while(j+h < n && i+h < n && str[j+h] == str[i+
h])
35 {
36 lcp[isa[i]] =
h
37 h +=
1
38 }
39 }
40 else
41 {
42 lcp[isa[i]] =
0
43 }
44 if h >
0 {h -=
1}
45 }
46 return lcp
47 }
48
49 func suffixArray(_ str:[Character],_ W:Int) ->
[Int]
50 {
51 let n:Int =
str.count
52 if n <=
1 {
return [Int](repeating:
0,count:n)}
53 var sa:[Int] = [Int](repeating:
0,count:n)
54 var s:[Int] = [Int](repeating:
0,count:n +
3)
55 for i
in 0..<
n
56 {
57 s[i] = str[i].ascii -
96
58 }
59 suffixArray(s, &sa, n, W+
1)
60 return sa
61 }
62
63 func suffixArray(_ s:[Int],_ sa:inout [Int],_ n:Int,_ K:Int)
64 {
65 let n0:Int = (n+
2)/
3
66 let n1:Int = (n+
1)/
3
67 let n2:Int = n/
3
68 let n02:Int = n0 +
n2
69
70 var s12:[Int] = [Int](repeating:
0,count:n02 +
3)
71 var sa12:[Int] = [Int](repeating:
0,count:n02 +
3)
72 var s0:[Int] = [Int](repeating:
0,count:n0)
73 var sa0:[Int] = [Int](repeating:
0,count:n0)
74
75 // generate positions of mod 1 and mod 2 suffixes
76 // the "+(n0-n1)" adds a dummy mod 1 suffix if n%3 == 1
77 let sup:Int = n + (n0 -
n1)
78 var i1:Int =
0
79 var j1:Int =
0
80 while(i1 <
sup)
81 {
82 if i1 +
1 <
sup {
83 s12[j1] = i1 +
1
84 j1 +=
1
85 }
86 if i1 +
2 <
sup {
87 s12[j1] = i1 +
2
88 j1 +=
1
89 }
90 i1 +=
3
91 }
92
93 // lsb radix sort the mod 1 and mod 2 triples
94 radixPass(s12, &sa12, s,
2, n02, K)
95 radixPass(sa12, &s12, s,
1, n02, K)
96 radixPass(s12, &sa12, s,
0, n02, K)
97
98 // find lexicographic names of triples
99 var name:Int =
0
100 var c0:Int = -
1
101 var c1:Int = -
1
102 var c2:Int = -
1
103
104 for i
in 0..<
n02
105 {
106 if s[sa12[i]] != c0 || s[sa12[i]+
1] != c1 || s[sa12[i]+
2] !=
c2
107 {
108 name +=
1
109 c0 =
s[sa12[i]]
110 c1 = s[sa12[i]+
1]
111 c2 = s[sa12[i]+
2]
112 }
113 if sa12[i] %
3 ==
1
114 {
115 // left half
116 s12[sa12[i]/
3] =
name
117 }
118 else
119 {
120 // right half
121 s12[sa12[i]/
3 + n0] =
name
122 }
123 }
124
125 // recurse if names are not yet unique
126 if name <
n02
127 {
128 suffixArray(s12, &
sa12, n02, name)
129 // store unique names in s12 using the suffix array
130 for i
in 0..<
n02
131 {
132 s12[sa12[i]] = i +
1
133 }
134 }
135 else
136 {
137 // generate the suffix array of s12 directly
138 for i
in 0..<
n02
139 {
140 sa12[s12[i]-
1] =
i
141 }
142 }
143
144 // stably sort the mod 0 suffixes from sa12 by their first character
145 var i2:Int =
0
146 var j2:Int =
0
147 while(i2 <
n02)
148 {
149 if sa12[i2] <
n0
150 {
151 s0[j2] =
3 *
sa12[i2]
152 j2 +=
1
153 }
154 i2 +=
1
155 }
156 radixPass(s0, &sa0, s,
0, n0, K)
157
158 // merge sorted sa0 suffixes and sorted sa12 suffixes
159 var p:Int =
0
160 var t:Int = n0 -
n1
161 var k:Int =
0
162 while(k <
n)
163 {
164 // pos of current offset 12 suffix
165 let i:Int = sa12[t] < n0 ? sa12[t] *
3 +
1 : (sa12[t] - n0) *
3 +
2
166 // pos of current offset 0 suffix
167 let j:Int =
sa0[p]
168 if sa12[t] < n0 ?
169 (s[i] < s[j] || s[i] == s[j] && s12[sa12[t]+n0] <= s12[j/
3]) :
170 (s[i] < s[j] || s[i] == s[j] && (s[i+
1] < s[j+
1] || s[i+
1] == s[j+
1] && s12[sa12[t]-n0+
1] <= s12[j/
3+
n0]))
171 {
172 // suffix from a12 is smaller
173 sa[k] =
i
174 t +=
1
175 if t ==
n02
176 {
177 // done --- only sa0 suffixes left
178 k +=
1
179 while(p <
n0)
180 {
181 sa[k] =
sa0[p]
182 p +=
1
183 k +=
1
184 }
185 }
186 }
187 else
188 {
189 // suffix from sa0 is smaller
190 sa[k] =
j
191 p +=
1
192 if p ==
n0
193 {
194 // done --- only sa12 suffixes left
195 k +=
1
196 while(t <
n02)
197 {
198 sa[k] = sa12[t] < n0 ? sa12[t] *
3 +
1 : (sa12[t] - n0) *
3 +
2
199 t +=
1
200 k +=
1
201 }
202 }
203 }
204 k +=
1
205 }
206 }
207
208 func radixPass(_ a:[Int],_ b:inout [Int],_ r:[Int],_ l:Int,_ n:Int,_ K:Int)
209 {
210 // counter array
211 var c:[Int] = [Int](repeating:
0,count:K +
1)
212 for i
in 0..<
n
213 {
214 // count occurrences
215 c[r[l + a[i]]] +=
1
216 }
217 var i:Int =
0
218 var sum:Int =
0
219 while(i <=
K)
220 {
221 // exclusive prefix sums
222 let t:Int =
c[i]
223 c[i] =
sum
224 sum +=
t
225 i +=
1
226 }
227 for i
in 0..<
n
228 {
229 b[c[r[l + a[i]]]] =
a[i]
230 c[r[l + a[i]]] +=
1
231 }
232 }
233 }
234
235 //Character扩展
236 extension Character
237 {
238 //Character转ASCII整数值(定义小写为整数值)
239 var ascii: Int {
240 get {
241 return Int(self.unicodeScalars.first?.value ??
0)
242 }
243 }
244 }
245
246 extension String {
247 // 截取字符串：指定索引和字符数
248 // - begin: 开始截取处索引
249 // - count: 截取的字符数量
250 func subString(_ begin:Int,_ count:Int) ->
String {
251 let start = self.index(self.startIndex, offsetBy: max(
0, begin))
252 let end = self.index(self.startIndex, offsetBy: min(self.count, begin +
count))
253 return String(self[start..<
end])
254 }
255 }
转载于:https://www.cnblogs.com/strengthen/p/10852170.html
