优化字符串范围搜索
优化字符串范围搜索
提问于 2020-05-27 00:42:21
我目前正在研究一种算法来查找目标字符串的所有范围。
示例：
Input: s = "acfacfacf", target = "acf"
Output: [(0, 3), (3, 6), (6, 9)]
Note: the upperBound is not an index of the subarray.这是我目前的解决方案：
extension String {
func allRanges(of string: String) -> [(Int, Int)] {
var ranges = [(Int, Int)]()
var set: Set<Int> = []
let chars = Array(self)
let target = Array(string)
for index in 0..<chars.count {
if chars[index] == string.first { set.insert(index) }
for i in set {
if index-i < target.count && chars[index] == target[index-i] {
if index-i == target.count-1 {
ranges += [(i, index+1)]
}
} else {
set.remove(i)
}
}
}
return ranges
}
}该算法在诸如"acfacfacf“这样的字符串上做得很好，但是对于”(目标为"aaaaaaaa“)这样的字符串，该算法做得很差，预期的结果是：
[(0, 8), (1, 9), (2, 10), (3, 11), (4, 12), (5, 13), (6, 14), (7, 15), (8, 16), (9, 17)]这里有什么可以做的优化吗？
编辑:还有。我知道在这里使用元组不是很迅速，但这不是我在这里最关心的问题。
回答 2
Stack Overflow用户
回答已采纳
发布于 2020-05-27 02:54:36
您可以迭代您的集合索引，删除最后n个元素(集合的大小减去一个)，检查子序列元素是否等于另一个集合，如果真返回范围，则返回nil：
extension Collection where Element: Equatable {
func indices<C: Collection>(of collection: C) -> [Index] where C.Element == Element {
let size = collection.count
return indices.dropLast(size-1).filter {
self[$0..<index($0, offsetBy: size)].elementsEqual(collection)
}
}
func ranges<C: Collection>(of collection: C) -> [Range<Index>] where C.Element == Element {
let size = collection.count
return indices.dropLast(size-1).compactMap {
let range = $0..<index($0, offsetBy: size)
return self[range].elementsEqual(collection) ? range : nil
}
}
}您还可以尝试使用集合的方法starts(with:)对其进行优化，以避免在每次迭代中偏移集合索引：
func starts<PossiblePrefix>(with possiblePrefix: PossiblePrefix) -> Bool where PossiblePrefix : Sequence, Self.Element == PossiblePrefix.Elementextension Collection where Element: Equatable {
func ranges<C: Collection>(of collection: C) -> [Range<Index>] where C.Element == Element {
let size = collection.count
return indices.dropLast(size-1).compactMap {
self[$0...].starts(with: collection) ? $0..<index($0, offsetBy: size) : nil
}
}
}或压缩可能范围内的上下指数：
extension Collection where Element: Equatable {
func ranges<C: Collection>(of collection: C) -> [Range<Index>] where C.Element == Element {
let k = collection.count-1
return zip(indices.dropLast(k),indices.dropFirst(k)).compactMap {
self[$0...].starts(with: collection) ? $0 ..< index(after: $1) : nil
}
}
}Stack Overflow用户
发布于 2020-05-27 16:10:04
建立在利奥的岗位上。执行.start(...)和index(...)似乎有一些不必要的工作。这可以通过以下方法进一步优化
extension Collection where Element: Equatable {
func ranges<C: RandomAccessCollection>(of collection: C) -> [Range<Index>] where C.Element == Element {
let size = collection.count
return indices.dropLast(size-1).compactMap { idx in
var i = idx
var match = false
collection.drop { element in
match = element == self[i]
i = index(after: i)
return match
}
return match ? idx..<i : nil
}
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62033684
复制相关文章
相似问题
腾讯云开发者
