は、私は、文字列アルゴリズムについてですCLRSブックから運動32.1から2を解決しようとしています

Question

に一致する私のコードの大きな-O、素朴なパターンを推定し、素朴なパターン検索

パターン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」に設定されているすべての文字を含むテキストを想像し、私は（第2ループにOで、毎回のダイビングますk * n）。

アルゴリズムのbig-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条件がテキストの各文字に対して1回だけ実行されるためです（内部ループが終了または終了した後、最後の位置の後に外部ループを開始することに注意してください）。

P .:ループの複雑さを乗算することはしばしば正しいことですが、可能な限り厳密に境界を定めることはできません。