估計我的代碼大O，天真模式匹配

Question

我試圖從CLRS的書，這是關於字符串算法，天真模式搜索

假設解決練習32.1-2，在模式P中的所有字符是不同的。顯示如何加速 NAIVE-STRING-MATCHER在n字符文本上在時間O（n）上運行。

所以我試圖優化我想出的天真蠻力解決方案，但我不認爲我可以做得更好，以減少O（n）的整體運行時間。

<?php 

//naive search 
$a = array('a', 'b', 'u', 'c'); 
$b = array('a','b','u','c','a','b','u','c','b','a','b','u','c','b', 'a', 'b','c'); 
//index  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
$n = count($b); 
$k = count($a); 
$counter = 0; 

    for($i=0;$i<$n - $k ;$i++){ // big- O (n) 


//since its "exact string matching problem" i am testing here so i don't dive into second loop unless the ith character of B is matching the first char of the pattern 

    if($b[$i] == $a[0]){ 
      for($j=$i; $j<$k; $j++){ // big O(k) 
       if($b[$j] == $a[$j]) 
        $bool = true; 
       else { 
        $bool = false; 
        break; 
       } 
      } 
      if($bool){ 
       echo "Found at index: ".$i."<br>"; 
       $counter++; 
      } 
// since pattern match cant overlap with another one, so when one is found jump by K iteration, here is all what I could do about the pattern's value being distinct, is there any possible optimization I can do 
      $i = $i + $k - 1; 
     } 


    } 

echo $counter; 
?> 

我肯定減少了運行時間爲這個特定實例，但是想象一下最壞的情況下，其所有字符設置爲「A」一文中，我將深入第二循環的每一個是O時間（ K * N）。

什麼是算法的大O？ ，我可以得到更有效的解決方案嗎？

Answer 1

你也明白了吧（「模式匹配不能與另一個重疊」）。 像這樣的東西應該主循環工作：

for($i=0;$i<$n - $k ;$i++){ 
      for($j=0; $j<$k; $j++){ 
       $last_matched = $j + $i; 
       if($b[$j + $i] == $a[$j]) 
        $bool = true; 
       else { 
        $bool = false; 
        break; 
       } 
      } 
      if($bool){ 
       echo "Found at index: ".$i."<br>"; 
       $counter++; 
      } 
      // this line is important 
      $i = $last_matched + 1; 
     } 

注意的重要防線。 這裏我們告訴算法，在我們以前的比賽失敗（或完成）之後開始下一次匹配嘗試。 這是因爲模式具有不同的字符，並且不可能如果您已經匹配j個字符，然後不匹配j + 1個字符，那麼真正的匹配將重疊此區域（如果它們重疊，模式中的某些字符應該是相同，這是矛盾的）。

現在改變算法的複雜度將是O（n）。這是因爲對於文本的每個字符，內部循環中的if條件只會執行一次（請記住，內部循環完成或中斷後，我們會在最後一個位置之後開始外部循環）。

P.S .:乘以循環的複雜性往往是對的，但你並不總能得到最緊密的界限。