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

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

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

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

这个对应着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的时候，已经不相等了。

看下图：
















a b c（i=2）
a b k (j=2)

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
















a b（i = 1） c
null a（j = 0） b

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

#####算法实现：

  1. var strStr = function (str, pattern) { 
  2.     var i = 0, j = 0
  3.     while (i < str.length && j < pattern.length ) { 
  4.         if (str[i] === pattern[j]) { 
  5.             i++;
  6.             j++  
  7.         } else { 
  8.             // 不相等的情况下，i 需要回到 起点的下一个位置 ，j 需要回到 0
  9.             // 然后重新新开始比较
  10.             // i的回溯起点，画个图就清楚了
  11.             i = i - j + 1
  12.             j = 0
  13.         }
  14.     }
  15.     if (j == pattern.length) return i - j
  16.     return -1
  17. }

####TRICKS

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

  1. var strStr = function (str, pattern, position) { 
  2.     var i = position, j = 0
  3.     while (i < str.length && j < pattern.length ) { 
  4.         if (str[i] === pattern[j]) { 
  5.             i++;
  6.             j++  
  7.         } else { 
  8.             // 不相等的情况下，i 需要回到 起点的下一个位置 ，j 需要回到 0
  9.             // 然后从新开始比较
  10.             // i的回溯起点，画个图就清楚了
  11.             i = i - j + 1
  12.             j = 0
  13.         }
  14.     }
  15.     if (j == pattern.length) return i - j
  16.     return -1
  17. }

so cool!!!

时间复杂度分析

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

最好的情况下:

  1. var str = 'aaaaaaaaab'
  2.     var pattern = 'aaaa'

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

最坏的情况下:

  1. var str = 'aaaaaaaaab' // 长度为10, m = 10
  2.     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 算法

发表评论

表情：
评论列表 （有 0 条评论，92人围观）

还没有评论，来说两句吧...

相关阅读