给定文本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_none brightness_4 txt[] = "AABCCAADDEE"; pat[] = "FAA";
最佳情况下的比较次数为O(n)
。
什么是最坏的情况?
1)当文本和图案的所有字符相同时。
filter_none brightness_4 txt[] = "AAAAAAAAAAAAAAAAAA"; pat[] = "AAAAA";
2)当最后一个字符不同时,也会出现最坏情况。
filter_none brightness_4 txt[] = "AAAAAAAAAAAAAAAAAB"; pat[] = "AAAAB";
最坏情况下的比较次数是O(m *(n-m + 1))
。虽然具有重复字符的字符串不太可能出现在英文文本中,但它们很可能出现在其他应用程序中(例如,在二进制文本中)。
相关推荐:《PHP教程》
以上就是PHP实现用于模式搜索的朴素算法(字符串匹配算法)的详细内容,更多请关注php中文网其它相关文章!
已抢17174个
抢已抢50123个
抢已抢121174个
抢已抢184469个
抢已抢66314个
抢已抢350767个
抢