朴素字符串匹配

字符串

说明

从每个起点逐字符比对；最坏时间 O(nm)。

分析

从文本的每个可能起点开始，直接比较长度为 m 的窗口与模式串。它没有预处理成本，短文本或短模式下很实用，但大量重复前缀会产生反复比较。

图解推演

在 hello gopher 中匹配 gopher，候选起点只能从 0 到 n−m；起点 6 的六字节窗口首次完全相等。窗口首字节失配可以很快排除，但文本 aaaa… 与模式 aaaab 会在每个起点比较接近 m 次，所以最坏 O(nm)。空模式按当前实现返回 0。

查看图表代码

适用前提与边界

这个 Go 例子按 UTF-8 字节查找并返回字节下标。

示例输入与调用

fmt.Println(Find("hello gopher", "gopher"))

运行输出

6

完整 Go 示例

package main

import "fmt"

func Find(text, pattern string) int {
	for i := 0; i+len(pattern) <= len(text); i++ {
		if text[i:i+len(pattern)] == pattern {
			return i
		}
	}
	return -1
}

func main() {
	fmt.Println(Find("hello gopher", "gopher"))
}