[关闭]
@JunQiu 2018-09-18T13:14:08.000000Z 字数 896 阅读 470

string_kmp/bm

summary_2018/08 algorithm


1、日常

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

2、技术

2.1、KMP算法

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

2.2、BM算法

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注