数据结构与算法-字符串匹配BF算法【六】

Love The Way You Lie 2023-06-30 15:53 25阅读 0赞

标签：`BF算法` `简单穷举法` `实现strStr`

--------------------

字符串的匹配算法，题目是什么呢，给定一个字符串（str） 和一个模式串（pattern）找出模式串在给定的字符串里面的位置，若不存在则返回 -1。

这个对应着[leetcode第28题][leetcode_28], 当然很多高级语言都实现了这个方法，比如javascript里面，使用`str.indexOf(pattern)`就直接求解了，但是这个题目的要求是实现这个方法，不是调用别人已经写好的方法。

## BF 算法 ##

> BF（brute-force）算法 简单穷举法

比如咱们给定的字符串str是 `abcokabkoh` 需要匹配的模式串pattern为`abk`。我们从str和pattern的第一个字符开始, str的的索引从0开始，pattern的索引也从0开始，`i==0` `j==0` 相等，则`(i++) && (j++)`  
当i==2的时候，已经不相等了。

看下图：

这时候我们需要将i 和 j 回溯，也就是说从i 为 0开始的匹配已经失败，需要从i为1也就是b开始比较，这时候模式串也必须从0开始匹配。应该如下：

实际上就是模式串往后滑动了一个位置。可以理解为str不变化，每一次只是pattern在str下方滑动，i为str的索引，j为pattern的索引，如果遇到不等，都需要回溯\[需要从头开始比较\]，i 变为 `i-j + 1`, j 变为 `0`, 从i开始的地方的下一个位置重新和pattern开始比较。

> \#\#\#\#\#算法实现：

var strStr = function (str, pattern) { 
        var i = 0, j = 0
        while (i < str.length && j < pattern.length ) { 
            if (str[i] === pattern[j]) { 
                i++;
                j++  
            } else { 
                // 不相等的情况下，i 需要回到 起点的下一个位置 ，j 需要回到 0
                // 然后重新新开始比较
                // i的回溯起点，画个图就清楚了
                i = i - j + 1
                j = 0
            }
        }
        if (j == pattern.length) return i - j
        return -1
    }

> \#\#\#\#TRICKS

咱们对上面的方法进行改进，传入一个position参数，然后指定给i，这样就可以实现需求，从position开始【包括position位置】是否包含pattern字符串。

var strStr = function (str, pattern, position) { 
        var i = position, j = 0
        while (i < str.length && j < pattern.length ) { 
            if (str[i] === pattern[j]) { 
                i++;
                j++  
            } else { 
                // 不相等的情况下，i 需要回到 起点的下一个位置 ，j 需要回到 0
                // 然后从新开始比较
                // i的回溯起点，画个图就清楚了
                i = i - j + 1
                j = 0
            }
        }
        if (j == pattern.length) return i - j
        return -1
    }

so cool!!!

> #### 时间复杂度分析 ####

假定 str字符串长度为m， pattern模式串的长度为n

最好的情况下:

var str = 'aaaaaaaaab'
        var pattern = 'aaaa'

模式串就在str的第一位，那么这时候时间复杂度为O(n)

最坏的情况下:

var str = 'aaaaaaaaab' // 长度为10, m = 10
        var pattern =   'aaac'  // 长度为4, n = 4

这时候执行的时间为 `(m-n) * n` i 从 0 到 5 每一次都比较了4次，不等。

这时候i回溯到6，j回溯到0，然后最后又比较了4次， 到i已经达到str的长度，while循环退出。 所以应该加上最后的n次。

因此最坏的情况是 `O((m-n)*n + n) = O((m-n+1)*n)` 当 `n<<m` 当m无限大的情况下，n远小于m的情况下，可以近似的认为时间复杂度为`O(mn)`

--------------------

但是BF算法进行了很多无效的重复比较，看下图：

![bf算法的缺点][bf]  
资料： [王桌老师-串的匹配算法 BF 算法][-_ BF]

[leetcode_28]: https://leetcode.com/problems/implement-strstr/
[bf]: https://img-blog.csdnimg.cn/20200118155429519.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E1NTM0Nzg5,size_16,color_FFFFFF,t_70
[-_ BF]: https://www.bilibili.com/video/av34404686