模式匹配算法

模式匹配是我们日常工作中最常见的任务之一。PHP 内置了对正则表达式的支持，在大多数情况下，我们依靠正则表达式和内置的字符串函数来解决此类问题的正则需求。PHP 有一个名为 strops 的现成函数，可以返回文本中字符串首次出现的位置。由于它只返回第一次出现的位置，我们可以尝试编写一个函数来返回所有可能的位置。我们将首先探索 "暴力" 方法，即用模式字符串检查实际字符串的每个字符。下面的函数将为我们完成这项工作：

Unresolved include directive in modules/ROOT/pages/ch11/ch11-02.adoc - include::example$Chapter11/2.php[]

方法非常简单。我们从实际字符串的 0 位置开始，一直搜索到 $N-$M 位置，其中 $M 是我们要搜索的模式的长度。即使在没有匹配模式的最坏情况下，我们也不需要搜索整个字符串。现在，让我们调用带有参数的函数：

Unresolved include directive in modules/ROOT/pages/ch11/ch11-02.adoc - include::example$Chapter11/2.php[]

输出结果如下：

Pattern found at index : 0
Pattern found at index : 9
Pattern found at index : 16

如果我们查看一下 $txt 字符串，就会发现我们的模式 AABA 在树上出现。第一个出现在字符串的开头，第二个出现在字符串的中心，第三个出现在字符串的末尾。我们编写的算法需要 O((N - M) * M) 的复杂度，其中 N 是文本的长度，M 是我们要搜索的模式的长度。如果我们愿意，可以使用一种流行的字符串匹配算法 Knuth-Morris-Pratt(KMP) 来提高这种匹配的效率。