PHP如何實(shí)現(xiàn)用于模式搜索的樸素算法

小編給大家分享一下PHP如何實(shí)現(xiàn)用于模式搜索的樸素算法，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

給定文本txt [0..n-1]和模式pat [0..m-1]，編寫一個(gè)函數(shù)搜索（char pat []，char txt []），在txt中打印所有出現(xiàn)的pat [] []。你可以假設(shè)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 ）搜索是計(jì)算機(jī)科學(xué)中的一個(gè)重要問題。當(dāng)我們?cè)谟浭卤尽?word文件、瀏覽器或數(shù)據(jù)庫中搜索字符串時(shí)，使用模式搜索算法來顯示搜索結(jié)果。

樸素模式搜索：
將模式逐個(gè)滑過文本并檢查是否匹配。如果找到匹配項(xiàng)，則再次滑動(dòng)1以檢查后續(xù)匹配項(xiàng)。

PHP代碼：

<?php 
// 樸素模式搜索算法
  
function search($pat, $txt) 
{ 
    $M = strlen($pat); 
    $N = strlen($txt); 
  
    for ($i = 0; $i <= $N - $M; $i++) 
    { 
  
        // 對(duì)于當(dāng)前索引i，請(qǐng)檢查模式匹配
        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

什么是最好的情況？

當(dāng)Pattern模式的第一個(gè)字符根本不存在于文本中時(shí)，會(huì)出現(xiàn)最佳情況。

filter_none
brightness_4
txt[] = "AABCCAADDEE"; 
pat[] = "FAA";

最佳情況下的比較次數(shù)為O（n）。

什么是最壞的情況？

1）當(dāng)文本和圖案的所有字符相同時(shí)。

filter_none
brightness_4
txt[] = "AAAAAAAAAAAAAAAAAA"; 
pat[] = "AAAAA";

2）當(dāng)最后一個(gè)字符不同時(shí)，也會(huì)出現(xiàn)最壞情況。

filter_none
brightness_4
txt[] = "AAAAAAAAAAAAAAAAAB"; 
pat[] = "AAAAB";

最壞情況下的比較次數(shù)是O（m *（n-m + 1））。雖然具有重復(fù)字符的字符串不太可能出現(xiàn)在英文文本中，但它們很可能出現(xiàn)在其他應(yīng)用程序中（例如，在二進(jìn)制文本中）。

以上是PHP如何實(shí)現(xiàn)用于模式搜索的樸素算法的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！