[Swift]LeetCode1044. 最长重复子串 | Longest Duplicate Substring

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（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^5
S consists of lowercase English letters.

给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。

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

示例 1：

输入："banana"
输出："ana"

示例 2：

输入："abcd"
输出：""

提示：

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

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 }