PHP实现用于模式搜索的朴素算法（字符串匹配算

例子：

输入: 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 $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））。虽然具有重复字符的字符串不太可能出现在英文文本中，但它们很可能出现在其他html' target='_blank'>应用程序中（例如，在二进制文本中）。

相关推荐：《PHP教程》

以上就是PHP实现用于模式搜索的朴素算法（字符串匹配算法）的详细内容，PHP教程

郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。