PHP实现用于模式搜索的朴素算法（字符串匹配算法）
PHP实现用于模式搜索的朴素算法（字符串匹配算法）
内容导读
收集整理的这篇技术教程文章主要介绍了PHP实现用于模式搜索的朴素算法（字符串匹配算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1755字，纯文字阅读大概需要3分钟。
内容图文
给定文本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实现用于模式搜索的朴素算法（字符串匹配算法）的详细内容，更多请关注Gxl网其它相关文章！
内容总结
以上是为您收集整理的PHP实现用于模式搜索的朴素算法（字符串匹配算法）全部内容，希望文章能够帮你解决PHP实现用于模式搜索的朴素算法（字符串匹配算法）所遇到的程序开发问题。 如果觉得技术教程内容还不错，欢迎将网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
