PHP完成用于形式搜刮的质朴算法（字符串婚配算法）【php教程】,PHP,朴素算法

给定文本 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完成用于形式搜刮的质朴算法（字符串婚配算法）的细致内容，更多请关注ki4网别的相干文章！