美文网首页
字符串匹配算法总结

字符串匹配算法总结

作者: Breezes | 来源:发表于2022-01-04 11:14 被阅读0次

根据袁厨的算法小屋字符串匹配部分做的笔记

BF(Brute Force)

暴力匹配,所谓暴力就是不考虑性能要求,从主串的第0个字符与模式串进行匹配,如果模式串匹配失败,则主串移动到下一个字符,效率非常差,力扣的题目其中一个用例时4万个字符中查找,提示超时,在xocde也会执行很久

func strStrBF(haystack: String,needle: String) -> Int {
        
        //特殊情况
        if needle.count == 0 {return 0}
        if (needle.count >  haystack.count) {
            return -1
        }
        
        for i in 0..<haystack.count - needle.count + 1 {
            for j in 0..<needle.count {
                let iS = haystack.index(haystack.startIndex, offsetBy: i+j)
                let jS = needle.index(needle.startIndex, offsetBy: j)
                
                //发现不相等,break
                if (haystack[iS] != needle[jS]) {
                    break
                }
                
                //匹配成功
                if j == needle.count - 1 {
                    return i
                }
                
                
            }
        }
        
        return -1
    }

BM(Boyer-Moore)

BM算法根据BF算法进行优化,BF主串每次只能位移一位,而BF可以移动多位,根据是坏字符和好后缀法则
BF算法是从左往右,BM是从右往左

坏字符

从右开始匹配,如果发现匹配失败,就将主串中的这个匹配失败的字符称为坏字符,然后到模式串中查找
1.如果没有在模式串中找到,则直接将模式串右移到坏字符的后面一位
2.如果在模式串中找到:
(1)如果找到一个,则根据模式串中找到的坏字符和主串的字符对齐
(2)如果找到多个,则以最右的为准(为什么?)
3.如果要移动的位置是负数,则需要使用好后缀法则

图示:
发现坏字符f.png
查询模式串T发现没有坏字符,移动模式串到坏字符后一位,也就是g的位置.png
如果在模式串中发现坏字符fpng
模式串中找到的坏字符和主串的坏字符对齐.png
如果在模式串中找到多个坏字符的情况,则以最右为准.png
移动位数为负的情况.png

好后缀

1.如果模式串中含有好后缀,无论是中间还是头部都可以按照规则移动,如果在好后缀出现多次,则以右侧的好后缀为准;
2.如果模式串头部含有好后缀子串则可以按照规则移动,如果中间含有子串不可以;
3.如果不存在好后缀(尾部就不匹配的情况),则以坏字符为准
4.计算时分别计算好后缀和坏字符比较两个大小,选择进行移动

图示:
好后缀cac.png
模式串完全含有好后缀✅.png
模式串头部含有好后缀子串✅.png
模式串中间含有好后缀子串❌.png

Swift代码⬇️

    func strStrBM(haystack: String, needle: String) -> Int {
        if needle.count == 0 {return 0}
        if haystack.count == 0 {return -1}
        
        return bm(haystack: haystack, needle: needle)
    }
    
    func bm(haystack: String, needle: String) -> Int {
        var bc = Array(repeating: -1, count: 256)
        badChar(needle: needle, bc: &bc)
        
        var suffix_index = Array(repeating: -1, count: needle.count)
        var prefix = Array(repeating: false, count: needle.count)
        goodSuffix(needle: needle, suffix: &suffix_index, prefix: &prefix)
        
        var i = 0
        
        while i <= haystack.count - needle.count {
            
            var j = needle.count - 1
            
            while j >= 0 {
                let haystackCur = haystack[haystack.index(haystack.startIndex, offsetBy: i + j)]
                let needleCur = needle[needle.index(needle.startIndex, offsetBy: j)]
                
                if haystackCur != needleCur {//找到坏字符
                    break
                }
                j -= 1
            }
            
            //模式串遍历完毕,匹配成功
            if j < 0 {
                return i
            }
            
            //计算坏字符需要移动的距离
            let x = j - bc[Int(haystack[haystack.index(haystack.startIndex, offsetBy: i + j)].asciiValue!)]
            var y = 0
            
            if y < needle.count - 1 && needle.count - 1 - j > 0 {
                //计算好后缀需要移动的距离
                y = move(j: j, m: needle.count, suffix_index: suffix_index, ispre: prefix)
            }
            
            //比较大小进行移动
            i = i + max(x, y)
            
        }
        
        return -1
    }
    
    func move(j: Int, m: Int, suffix_index: [Int], ispre: [Bool]) -> Int {
        //好后缀长度
        let k = m - 1 - j
        
        //第一种情况,如果含有长度为k的好后缀,返回移动位数
        if suffix_index[k] != -1 {
            return j - suffix_index[k] + 1
        }
        
        //第二种情况,头部含有好后缀字串,则找头部为好后缀字串的最大长度,从长度最大的淄川开始
        for r in (j+2)..<m {
            //如果是头部
            if ispre[m-r] == true {
                return r
            }
        }
        
        
        //第三种情况,没有发现好后缀的匹配的串,或者是头部为好后缀字串,则移动整个匹配串的长度
        return m
        
    }
    
    
    //坏字符情况下的移动位数
    func badChar(needle: String, bc: inout [Int]) {
        for i in 0..<needle.count {
            let index = needle.index(needle.startIndex, offsetBy: i)
            if let ascii = needle[index].asciiValue {
                bc[Int(ascii)] = i
            }
        }
    }
    
    //好后缀情况下的移动位数
    func goodSuffix(needle: String, suffix: inout [Int], prefix: inout [Bool]) {
        
        for i in 0..<needle.count-1 {
            var j = i
            var k = 0
            
            while j >= 0 && needle[needle.index(needle.startIndex, offsetBy: j)] == needle[needle.index(needle.startIndex, offsetBy: needle.count - 1 - k)] {
                j -= 1
                k += 1
                suffix[k] = j + 1
            }
            
            if j == -1 {
                prefix[k] = true
            }
            
            
        }
    }

KMP

找到模式串所有的最长前后缀,存入next数组,通过next数组进行移动

    func strStrKMP(haystack: String, needle: String) -> Int {
        if needle.count == 0 {return 0}
        if haystack.count == 0 {return -1}
        
        return kmp(haystack: haystack, needle: needle)
    }
    
    func kmp(haystack: String, needle: String) -> Int {
        let next = nextList(needle: needle)
        var j = 0
        
        for i in 0..<haystack.count { //i
            let iIndex = haystack.index(haystack.startIndex, offsetBy: i)
            var jIndex = needle.index(needle.startIndex, offsetBy: j)

            while j > 0 && haystack[iIndex] != needle[jIndex] {

                j = next[j - 1] + 1
                if needle.count - j + i > haystack.count {
                    return -1
                }
            
                jIndex = needle.index(needle.startIndex, offsetBy: j)
            }
            if haystack[iIndex] == needle[jIndex] {
                j += 1
            }
            if j == needle.count {
                return i - needle.count + 1
            }
        }
        return -1
    }
    
    func nextList(needle: String) -> [Int] {
        //定义next数组
        var next = Array(repeating: -1, count: needle.count)
        
        var k = -1;
        for i in 1..<needle.count {
            
            while k != -1 && needle[needle.index(needle.startIndex, offsetBy: k+1)] != needle[needle.index(needle.startIndex, offsetBy: i)] {
                k = next[k]
            }
            
            if needle[needle.index(needle.startIndex, offsetBy: k+1)] == needle[needle.index(needle.startIndex, offsetBy: i)] {
                k += 1
            }
            
            next[i] = k
        }
        return next
    }
图示
计算next数组.png

相关文章

  • KMP字符串匹配算法

    KMP字符串匹配算法 先总结一下之前的几种字符串匹配算法 1 BF算法, 最简单的字符串匹配算法, 可以直接使用s...

  • 字符串匹配算法总结

    字符串匹配算法总结 所有代码集合 在一个主串中匹配模式串 BF算法   最简单的使用strcmp逐个匹配的算法, ...

  • 字符串匹配

    indexOf 底层就是使用字符串匹配算法 字符串匹配算法很多 BF( Brute Force)算法 暴力匹配算...

  • KMP算法文章合集

    字符串的查找:朴素查找算法和KMP算法 暴力匹配算法与KMP算法(串的匹配) 字符串查找算法BF和KMP 字符串匹...

  • 一些有关算法的

    字符串模式匹配算法 字符串的KMP算法详解部分匹配表(即)向右移一位就可以得到next数组。字符串模式匹配算法 R...

  • 字符串匹配算法

    场景:字符串A为主串,字符串B为模式串,比较字符串B是否能够在字符串A中进行匹配? 匹配算法:BF算法和RK算法。...

  • 字符串匹配算法

    以下为学习 《数据结构与算法之美 -- 字符串匹配》 的记录。 BF算法 即暴力匹配算法,循环遍历匹配。 RK算法...

  • 2022-01-25

    1.字符串匹配BM算法 在文本中查找字符串匹配算法,坏字符串规则和好后缀规则坏字符串规则: 从后往前匹配,第一个不...

  • 20-字符串匹配

    字符串匹配 这章节,我们会讲到几大典型的字符串匹配算法 BF算法 BF算法是最最符合正常人逻辑思维的一种匹配模式,...

  • leetcode字符串匹配算法之KMP算法

    本篇介绍一种高效的字符串匹配算法——KMP算法。 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J....

网友评论

      本文标题:字符串匹配算法总结

      本文链接:https://www.haomeiwen.com/subject/zavyqrtx.html