string_kmp/bm

summary_2018/08 algorithm

1、日常

1.1、字符串搜索算法：KMP、BM算法

2、技术

2.1、KMP算法

• 思想：不匹配时本身就包含足够的信息来确定下一个匹配将在哪里，从而避免重新检查先前匹配的字符。
  
  • 算法的思想主要是理解前缀和后缀的最长的共有元素的长度（参考）
  • 主要的难点在于如何使用递归的思想求解next数组（参考1、参考2）
  • 算法实现

// "前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例:
　　－　"A"的前缀和后缀都为空集，共有元素的长度为0；
　　－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
　　－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
　　－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
　　－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
　　－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
　　－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
Tips:最简单的理解就是当在某个匹配失败的时候子串最大可以移动多少，其实上面就是完成这件事，共有元素最大长度l即移动后的效果，而我们需要移动的长度为 已匹配的字符数 - l

2.2、BM算法

• 思想：通过坏字符和好后缀两种策略相结合的方式，找出子串可以移动的最大距离，尽可能的提高搜索效率。（比如一些文本编辑器/grep中都有使用）
• 特点：
  
  • 从尾部开始开始比较，如果尾部字符不匹配，那么只要一次比较，就可以知道字符整体上是不是要找的结果。
  • "坏字符"（bad character），即不匹配的字符。"好后缀"（good suffix），即所有尾部匹配的字符串。
  • 和KMP算法相同，仅与搜索字串有关，可以使用打表的方式提前生成
• 算法实现
• 参考文献
  
  • 算法思想
  • 实现