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