KMP算法和BF算法
一般用来匹配字符串的问题,比如 abcdabcefgh 里 匹配 abce 这种情况
BF算法
百度百科: BF算法，即暴风(Brute Force)算法，是普通的模式匹配算法BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。
简而言之,就是暴力循环
1. 第一遍(匹配,i=0,j=0)
↓
原始串: a b c d a b c e f g h
匹配串: a b c e
↑
2. 第二遍(匹配,i=1,j=1)
↓
原始串: a b c d a b c e f g h
匹配串: a b c e
↑
3. 第三遍(匹配,i=2,j=2)
↓
原始串: a b c d a b c e f g h
匹配串: a b c e
↑
4. 第四遍(不匹配,原始串往后移一位,i=3,j=3)
↓
原始串: a b c d a b c e f g h
匹配串: a b c e
↑
5. 第五遍(不匹配,原始串往后移动一位,i=1,j=0)
↓
原始串: a b c d a b c e f g h
匹配串: a b c e
↑
6. 第六遍(不匹配,原始串往后移动一位,i=2,j=0)
↓
原始串: a b c d a b c e f g h
匹配串: a b c e
↑
7. 第七遍(不匹配,原始串往后移动一位,i=3,j=0)
↓
原始串: a b c d a b c e f g h
匹配串: a b c e
↑
8. 第八遍(匹配,继续往后比较,i=4,j=0)
↓
原始串: a b c d a b c e f g h
匹配串: a b c e
↑
9. 第九遍(匹配,继续往后比较,i=5,j=1)
↓
原始串: a b c d a b c e f g h
匹配串: a b c e
↑
10. 第十遍(匹配,继续往后比较,i=6,j=2)
↓
原始串: a b c d a b c e f g h
匹配串: a b c e
↑
11. 第十一遍(匹配,匹配串全部走完,说明全部匹配,返回,i=7,j=3)
↓
原始串: a b c d a b c e f g h
匹配串: a b c e
↑
BF算法简单易懂,但是并不怎么好,因为很多无用的重复操作,比如上面第四步发现不匹配后,第五六七其实都是无用的重复
代码:
str := "ababcababa"
ts := "ababa"
strLen := len(str)
tsLen := len(ts)
i,j := 0,0
for i < strLen && j < tsLen {
fit := i
if str[i] == ts[j] {
i++
j++
} else {
i = fit + 1
j = 0
}
}
if j == tsLen - 1 {
fmt.Println("匹配完成,起始下标是:",i-j)
return
} else {
fmt.Println("匹配完成,未匹配到")
return
}
KMP算法
百度百科: KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)
先来个白话版的
示例: 从主字符串”ababababsa” 里找到 子字符串 “abababsa”
1. 第一步
↓
主串: a b a b a b a b s a
下标: 0 1 2 3 4 5 6 7 8 9
子串: a b a b a b s a
↑
2. 第二步(挨个比较的过程省略,发现下标6的地方两个不一样)
↓
主串: a b a b a b a b s a
下标: 0 1 2 3 4 5 6 7 8 9
子串: a b a b a b s a
↑
3. 第三步(发现主字符串下标2~5 和 子字符串0~3 是一样的)
↓
主串: a b a b a b a b s a
下标: 0 1 2 3 4 5 6 7 8 9
子串: a b a b a b s a
↑
然后继续比较...
为什么要这样移动呢?
从第二步看
↓
主串: a b a b a b a b s a
下标: 0 1 2 3 4 5 6 7 8 9
子串: a b a b a b s a
↑
在下标6之前的 主字符串和子字符串是一毛一样的! 都是 ababab
而 ababab 的前缀集合(以开头字母为开始的连续的且不等于自身的字符串)和后缀集合(以结尾字母为结束的连续的且不等于自身的字符串)的交集 为 abab
子字符串的前缀集合: {a,ab,aba,abab,ababa}
子字符串的后缀集合: {b,ab,bab,abab,babab}
他俩的交集为 {ab,abab}
交集里最长的元素的长度 也叫做 PMT,上面这个结果abab的长度也就是4
为什么取最长的呢,因为最长的说明匹配度越高
因为主字符串的下标6之前和子字符串的是一样的
所以可以理解为
主字符串(下标6之前)的后缀(后4位)与子字符串(下标6之前)的前缀(前4位)是一样的!
所以 就有了第三步
此时保持主字符串的比较下标不动,子字符串下标挪到 4 的位置 再开始进行比较
↓
主串: a b a b a b a b s a
下标: 0 1 2 3 4 5 6 7 8 9
子串: a b a b a b s a
↑
那么问题来了, 这个PMT代码怎么求…..
j i
字符串： a b a b a b s a
串下标： 0 1 2 3 4 5 6 7
next ： 0 0
T[j]≠T[j] i++ next[i] = 0
j i
字符串： a b a b a b s a
串下标： 0 1 2 3 4 5 6 7
next ： 0 0 1
T[j]=T[j] i++ j++ next[i] = 1
j i
字符串： a b a b a b s a
串下标： 0 1 2 3 4 5 6 7
next ： 0 0 1 2
T[j]=T[j] i++ j++ next[i] = j + 1
j i
字符串： a b a b a b s a
串下标： 0 1 2 3 4 5 6 7
next ： 0 0 1 2 3
T[j]=T[j] i++ j++ next[i] = j+1
j i
字符串： a b a b a b s a
串下标： 0 1 2 3 4 5 6 7
next ： 0 0 1 2 3 4
T[j]=T[j] i++ j++ next[i] = j+1
j i
字符串： a b a b a b s a
串下标： 0 1 2 3 4 5 6 7
next ： 0 0 1 2 3 4 0
T[j]≠T[j] i++ j=0 next[i] = 0
j i
字符串： a b a b a b s a
串下标： 0 1 2 3 4 5 6 7
next ： 0 0 1 2 3 4 0 0
T[j]≠T[j] j = 0
最后得到 next[] = {0 0 1 2 3 4 0 0}
过程就是 i 和 j 进行比较,如果一样,数组值是之前的值+1,i和j都往后移动,如果不相同,j归位到0,i继续往后移动
一般为了方便计算,将数组整体右移一位,且把首位设置成 -1(你设置成任何负值都行,只是为了区分而已),最后一位抹去
那么 next 就是 {-1 0 0 1 2 3 4 0}
根据上面例子,当 下标为 6的时候 主字符串和子字符串不一样!
下标为6 对应 next数组里的 PMT的值是 4
所以 下次比较 是 主字符串 i的位置和 子字符串 4的位置进行比较!
代码:
str := "ababababca"
ts := "abababca"
next := getNext(ts)
next = next[:len(next)-1]
fmt.Println(next)
strLen := len(str)
tsLen := len(ts)
i,j := 0,0
for i < strLen && j < tsLen {
if j == -1 || str[i] == ts[j] {
i++
j++
} else {
j = next[j]
}
}
fmt.Println(j,tsLen)
if j == tsLen {
fmt.Println("匹配到")
} else {
fmt.Println("没有匹配到")
}
func getNext(str string) []int {
var next []int
next = append(next,-1)
next = append(next,0)
strLen := len(str)
fmt.Println(strLen)
i,j,s := 0,1,0
for j < strLen {
if str[i] == str[j] {
s++
i++
} else {
i = 0
s = 0
}
j++
next = append(next,s)
}
return next
}
