相关概念
主串
模式串
模式串<=主串
常用算法
BF
原理
我们在主串中，分别检查从0，1，2，....，到n-m位置的，n-m+1个字符串是否匹配。
特点
暴力匹配算法（最简单，最暴力的匹配算法），也叫朴素匹配算法。因为简单，不容易出错，容易实现，所以比较常用，而且现实场景字符串长度并不会很长，而且比较过程中发现不匹配就可以推到主串下一个字符继续匹配了，所以算法的时间复杂度远高于最坏O(m*n)的情况。在实际的开发过程中，绝大多数场景下，尤其针对小规模的字符串匹配，朴素的字符串匹配算法就够用了。
时间复杂度
O(m*n)
代码实现
package main
func Bf(ss, s string) (b bool, at int) {
n := len(ss)
m := len(s)
if m == 0 || n == 0 || m > n {
return b, at
}
for i := 0; i < n-m+1; i++ {
for j := i; j < i+m-1; j++ {
if ss[j] != s[j-i] {
break
}
b = true
at = j
return
}
}
return b, at
}
func Bf2(ss, s string) (b bool, at int) {
n := len(ss)
m := len(s)
if m == 0 || n == 0 || m > n {
return b, at
}
for i := 0; i < n-m+1; i++ {
if ss[i:i+m] == s {
b = true
at = i
return
}
}
return
}
func main() {
ss := "abcdjsfjsr"
s := "jsf"
b, at := Bf(ss, s)
println(b)
println(at)
b, at = Bf2(ss, s)
println(b)
println(at)
}
RK
原理
是对BF算法的一种优化，把每个子串用hash值来代替，模式串也计算出hash值，仅对hash值进行比较，当模式串与子串的hash值相等时，为避免hash冲突而相等时，在针对此子串跟模式串逐个对比一下即可。
难点
hash算法的设计，减少hash冲突。
HASH算法设计
a-z转化为26进制，转化为数字值，然后针对数字比较，这样比较快速。把每个元素的26进制，相加，这样比较可以有效避免计算机整数越界问题，但会出现大量hash冲突，比较模式串和子串hash相同后，要在详细逐一对比子串和模式串的每个元素，这样来解决hash冲突的问题。
时间复杂度
整个 RK 算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。第一部分，我们前面也分析了，可以通过设计特殊的哈希算法（复杂部分可以略过，就用简单的hash字符即可），只需要扫描一遍主串就能计算出所有子串的哈希值了，所以这部分的时间复杂度是 O(n)。（个人觉得此处缺少了计算模式串hash的时间。如果模式串很长的话，也会是一个O(n)，但不影响整体时间复杂度的统计。）
模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1)，总共需要比较 n-m+1 个子串的哈希值，所以，这部分的时间复杂度也是 O(n)。所以，RK 算法整体的时间复杂度就是 O(n)。
BM
算法思想
我们把模式串与主串匹配的过程，看成是模式串在主串上向后滑动比较的过程，当遇到不匹配的字符，bf和rk的做法是向后滑动一位，然后在从模式串头部开始重新比较，而BM主要是利用一些策略，计算出肯定不匹配的位数，让模式串尽最大位数的向后滑动，这样比较次数大幅减小，效率提高。
如：
主串：g t c d g t v y u
模式串：g t v
bf和rk做法：
第一次比较：c,v不等，向后滑动一位
g t c d g t v y u
g t v
第二次比较：t,g不等，向后滑动一位
g t c d g t v y u
g t v
第三次比较:c,gt,g不等，向后滑动一位
g t c d g t v y u
g t v
BM做法：
第一次比较：c,v不等，而且c不在模式串中出现，所以c的位置，跟子串都不匹配，子串移动到c后一位
g t c d g t v y u
g t v
第二次比较：
g t c d g t v y u
g t v
BM算法解析
坏字符规则
比较顺序，从后往前比较。没有好后缀的情况，最后一位就不匹配si，而坏字符在子串的前面xi（如果出现多个去最靠后的那个）。模式串相对主串的滑动位数为：si-xi 当前面没有匹配时候，xi取-1，（如果出现多个去最靠后的那个，及xi最大的那个，这样往后移动的位数最小，可以防止错过应有的匹配）。但是当有好后缀时候，xi反而比si数值还要大，si-xi 为负值，所以，单有坏字符策略还不够，还要有好后缀策略。
好后缀规则
在模式串中，查找跟好后缀匹配的另一个子串；在好后缀的后缀子串中，查找最长的、能跟模式串前缀子串匹配的后缀子串；
当既有坏字符，也有好后缀时候，取二者最大值，来向后滑动模式串，这就避免了si-xi为负数的场景。
KMP
原理
todo
代码实现
package main
import "fmt"
func KMP(ss, s string) (b bool, at int) {
n := len(ss)
m := len(s)
nexts := Nexts(s)
j := 0 // 模式串指针
for i:=0; i<n; i++ {
for j > 0 && ss[i] != s[j] {
j = nexts[j-1]+1
}
if ss[i] == s[j] {
if j == m-1 {
b = true
at = i-m+1
return
}
j = j+1
}
}
return b, at
}
func Nexts(s string) []int {
l := len(s)
next := make([]int, l)
for k := range next {
next[k] = -1
}
for i:=1;i<l;i++ {
j := next[i-1]
for j > -1 && s[j+1] != s[i] {
j = next[j]
}
if s[j+1] == s[i] {
j = j+1
}
next[i] = j
}
return next
}
func main() {
ss := "aacabdfghaacabcdefg"
s := "aacabc"
b, at := KMP(ss, s)
fmt.Println(b)
fmt.Println(at)
}
复杂度
空间复杂度
O(m) m为模式串长度
时间复杂度
O(m+n)
