• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1044.最长重复子串|LongestDuplicateSubstring

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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: 

Example 2:

Input: 

Note:

  1. 2 <= S.length <= 10^5
  2. S consists of lowercase English letters.

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

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

示例 1:

输入:"banana"
输出:"ana"

示例 2:

输入:"abcd"
输出:""

提示:

  1. 2 <= S.length <= 10^5
  2. 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
SWIFT问题很大,第4家受害银行浮出水面发布时间:2022-07-13
下一篇:
SwiftJson解析与model互转发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap