给定文本txt [0..n-1]和模式pat [0..m-1]，编写一个函数搜索（char pat []，char txt []），在txt中打印所有出现的pat [] []。你可以假设n> m。
例子：
输入: txt[] = "this is a test text" pat[] = "test"输出: pattern found at index 10输入: txt[] = "aabaacaadaabaaba" pat[] = "aaba"输出: pattern found at index 0 pattern found at index 9 pattern found at index 12
模式（pattern ）搜索是计算机科学中的一个重要问题。当我们在记事本、 word文件、浏览器或数据库中搜索字符串时，使用模式搜索算法来显示搜索结果。
朴素模式搜索：
将模式逐个滑过文本并检查是否匹配。如果找到匹配项，则再次滑动1以检查后续匹配项。
php代码：
<?php // 朴素模式搜索算法 function search($pat, $txt) { $m = strlen($pat); $n = strlen($txt); for ($i = 0; $i <= $n - $m; $i++) { // 对于当前索引i，请检查模式匹配 for ($j = 0; $j < $m; $j++) if ($txt[$i + $j] != $pat[$j]) break; // if pat[0...m-1] = // txt[i, i+1, ...i+m-1] if ($j == $m) echo "pattern found at index ", $i."\n"; } } $txt = "aabaacaadaabaaabaa"; $pat = "aaba"; search($pat, $txt);
输出：
pattern found at index 0 pattern found at index 9 pattern found at index 13
什么是最好的情况？
当pattern模式的第一个字符根本不存在于文本中时，会出现最佳情况。
filter_nonebrightness_4txt[] = "aabccaaddee"; pat[] = "faa";
最佳情况下的比较次数为o（n）。
什么是最坏的情况？
1）当文本和图案的所有字符相同时。
filter_nonebrightness_4txt[] = "aaaaaaaaaaaaaaaaaa"; pat[] = "aaaaa";
2）当最后一个字符不同时，也会出现最坏情况。
filter_nonebrightness_4txt[] = "aaaaaaaaaaaaaaaaab"; pat[] = "aaaab";
最坏情况下的比较次数是o（m *（n-m + 1））。虽然具有重复字符的字符串不太可能出现在英文文本中，但它们很可能出现在其他应用程序中（例如，在二进制文本中）。
相关推荐：《php教程》
以上就是php实现用于模式搜索的朴素算法（字符串匹配算法）的详细内容。