Chapter-11 TextMatch 第11章 文本匹配 - SimpleMatch 简单匹配

问题

在文本 text 中查找字符串 str 的位置（比如文本编辑器 VIM 中查找某个字符串的场景，设 text 长度为n， str 长度为 m ，该场景满足 n gt m ）。

解法

假设字符数组下标从 1 开始。简单匹配的方法是对于 text[1 cdots n] ，从第 1 个字符开始，依次比较 text[i+1 cdots i+m] 是否与 str[1 cdots m] 相等。若相等则 text[1 cdots n] 中匹配 str[1 cdots m] 的部分为 text[i+1 cdots i+m] ，否则继续从下一个位置 i+1 匹配。

实际大部分编程语言中字符数组的下标都从 0 开始。下面演示一个匹配的过程：

(1) 从 text 第 0 个字符开始匹配，有 text[0 cdots 2] = str[0 cdots 2]，text[3] ne str[3] ，继续匹配下一个字符；

(2) 从 text 第 1 个字符开始匹配，有 text[1] ne str[0] ，继续匹配下一个字符；

cdots

(3) 从 text 第 7 个字符开始匹配， text[7 cdots 10] = str[0 cdots 3] ，匹配成功，算法结束；

显然，对于 text 中的每个位置 i ，都需要进行一次匹配，而每次匹配的平均时间复杂度为 str 的长度 m 。因此该算法的时间复杂度为 O(m times n) ，实现简单但性能差。