面试题 / 算法

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
}

以上摘自： https://www.iphpt.com/detail/138

参考: