例子：

輸入: 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ù)庫(kù)中搜索字符串時(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 $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_nonebrightness_4txt[] = AABCCAADDEE pat[] = FAA 

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

什么是最壞的情況？

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

filter_nonebrightness_4txt[] = AAAAAAAAAAAAAAAAAA pat[] = AAAAA 

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

filter_nonebrightness_4txt[] = AAAAAAAAAAAAAAAAAB pat[] = AAAAB 

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

相關(guān)推薦：《PHP教程》

以上就是PHP實(shí)現(xiàn)用于模式搜索的樸素算法（字符串匹配算法）的詳細(xì)內(nèi)容，PHP教程

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請(qǐng)第一時(shí)間聯(lián)系我們修改或刪除，多謝。