1. KMP算法和BF算法

一般用来匹配字符串的问题,比如 abcdabcefgh 里 匹配 abce 这种情况

1.1. 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
    }

1.2. 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

参考:

results matching ""

    No results matching ""