【译】Swift算法俱乐部-暴力字符串搜索

栏目: Swift · 发布时间: 5年前

内容简介:本文是对:octopus:

本文是对 Swift Algorithm Club 翻译的一篇文章。

Swift Algorithm Clubraywenderlich.com 网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+:star:️,我初略统计了一下,大概有一百左右个的算法和数据结构,基本上常见的都包含了,是iOSer学习算法和数据结构不错的资源。

:octopus: andyRon/swift-algorithm-club-cn 是我对Swift Algorithm Club,边学习边翻译的项目。由于能力有限,如发现错误或翻译不妥,请指正,欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习 。当然也欢迎加:star:️, 。

本文的翻译原文和代码可以查看:octopus: swift-algorithm-club-cn/Brute-Force String Search

暴力字符串搜索(Brute-Force String Search)

如果不允许导入 Foundation 并且不能使用 NSStringrangeOfString() 方法,那么如何在纯Swift中编写字符串搜索算法呢?

目标是在 String 上实现 indexOf(pattern: String) 扩展,返回第一次出现的搜索模式的 String.Index ,如果在字符串中找不到模式,则返回 nil

例子:

// Input: 
let s = "Hello, World"
s.indexOf("World")

// Output:
<String.Index?> 7

// Input:
let animals = "  :turtle::blowfish::cow:  :whale2::dog::dolphin::tropical_fish::chicken::pig::octopus::cow:        :koala:  :goat:  "
animals.indexOf(":cow:")

// Output:
<String.Index?> 6

注意:牛的索引是6,而不是你想象的3,因为字符串为表情符号使用更多的存储空间。 String.Index 的实际值并不那么重要,只要它指向字符串中的正确字符。

这是暴力解决方案:

extension String {
    func indexOf(_ pattern: String) -> String.Index? {
        
        for i in self.indices {
            var j = i
            var found = true
            for p in pattern.indices {
                if j == self.endIndex || self[j] != pattern[p] {
                    found = false
                    break
                } else {
                    j = self.index(after: j)
                }
            }
            if found {
                return i
            }
        }
        return nil
    }
}

这将依次查看源字符串中的每个字符。 如果字符等于搜索模式的第一个字符,则内部循环检查模式的其余部分是否匹配,如果未找到匹配项,则外循环将从中断处继续。 重复此过程直到找到完全匹配或到达源字符串的结尾。

暴力方法运行正常,但效率不高(或漂亮)。 不过,暴力方法应该可以在小字符串上正常工作。 对于使用大块文本更好的智能算法,请查看 Boyer-Moore 字符串搜索。

作者:Matthijs Hollemans

翻译: Andy Ron

校对: Andy Ron


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Parsing Techniques

Parsing Techniques

Dick Grune、Ceriel J.H. Jacobs / Springer / 2010-2-12 / USD 109.00

This second edition of Grune and Jacobs' brilliant work presents new developments and discoveries that have been made in the field. Parsing, also referred to as syntax analysis, has been and continues......一起来看看 《Parsing Techniques》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

SHA 加密
SHA 加密

SHA 加密工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试