客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ Given a string Return any duplicated substring that has the longest possible length. (If Example 1: Input: Example 2: Input: Note:
给出一个字符串 返回任何具有最长可能长度的重复子串。（如果 示例 1： 输入："banana" 输出："ana" 示例 2： 输入："abcd" 输出："" 提示：
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 }
|
请发表评论