008 go 语言 大话数据结构 朴素(普速)的模式匹配算法

1 串的模式匹配 定义

在一篇文章中, 去找一个单词的定位问题, 这种子串的定位操作通常称作串的模式匹配

假设, 我们要从 主串 S="goodgoogle" 中, 找到 T="google" 这个子串的位置,
我们通常需要 以下的步骤

image.png
image.png image.png image.png image.png image.png

简单的说, 就是对 主串的每一个字符作为子串开头, 与要匹配的字符串进行匹配, 对主串做大循环, 每个字符串做T 长度的小循环, 直到匹配成功或者全部遍历完为止。

2 代码

2.1 思路总结

1. 结束条件
   1.1 主串的下标 > 主串的长度 -1的时候, 说明主串匹配完了, 需要结束
   1.2 子串的下标 > 子串的长度 -1 , 说明子串匹配完了, 需要结束

2.当主串 和子串中有一个字符不相等时, 主串需要回退到 上一次匹配的头位置的下一位, 因为 主串和子串走的步数相同, 所以 idxT = idxT - idxS +1 , 然后子串的下标归0
3.循环结束后, 如果子串的 下标 > 子串的长度 -1; 则说明子串完全匹配了, 需要返回 子串的头元素在主串中的下标, 因为匹配结束后, 子串在最后一个元素, 所以 下标 = 主串下标 - 子串长度

package main

import (
    "fmt"
)

// 朴素的模式匹配算法

func main() {
    S := "goodgoogle"
    //测试第一个元素
    // T := "g"
    //测试尾部元素
    // T := "e"
    //测试主串中不存在的元素
    // T := "f"
    // 测试复杂的子串
    // T := "google"
    //测试有迷惑性的子串
    // T := "oog"

    idx := indexOf(S, T)
    fmt.Println("idx---", idx)
}

/**
indexOf  S 为主串, T 为子串, 返回 T 在 S中的第一次出现的位置
**/
func indexOf(S string, T string) (ret int) {
    idxS := 0
    idxT := 0
    lenS := len(S)
    lenT := len(T)
    for {
        //主串循环到最后一个位置之后, 再结束
        //或者 子串循环完 , break
        if idxS > (lenS-1) || idxT >= lenT {
            break
        }

        if S[idxS] == T[idxT] {
            //比较的字符一样的时候,   主串 S 和子串 T 的下标都 +1
            idxS++
            idxT++
        } else {
            // 当不一样的时候, 子串下标归0 , 主串下标会到上一次匹配位置的后面一位
            // 因为 主串和子串走的步骤一样, 所以
            idxS = idxS - idxT + 1
            //子串的下标归0
            idxT = 0
        }

    }

    // 主串循环结束后, 根据子串的下标进行判断

    // 如果匹配OK, 则子串先比完, 子串的下标会跑到子串的最后一个位置
    if idxT > lenT-1 {
        //匹配OK的时候,   需要返回子串的首字母在主串的下标 ,  但是匹配结束后,  子串跑到了最后一位,  所以需要让主串的下标减去子串的长度, 以得到子串首字母在主串中的下标
        return idxS - lenT

    }

    //当匹配不OK的时候, 返回 -1
    return -1

}

3 算法优劣分析

image.png image.png image.png