欢迎光临杨雨的个人博客站!

杨雨个人网站-杨雨个人博客-杨照佳

杨雨个人博客网站

关注互联网和搜索引擎的个人博客网站

首页 > WEB开发 > PHP >

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

发布时间:2019-05-24  编辑:杨雨个人博客网站   点击:   

给定文本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

0b59774503099b4ad8124769a37f4a3.png

模式(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教程》 本文地址:http://itbyc.com/php/20096.html
转载请注明出处。

分享是一种快乐,也是一种美德:
博客首页 | WEB开发 | 网站运营 | CMS使用教程 滇ICP备14002061号-1