title: estimating my code big-O, naive pattern matching
body: <p>I am trying to solve exercise 32.1-2 from the CLRS Book, which is about string algorithms, naive pattern search</p>
  
  <blockquote>
    <p>Suppose that all characters in the pattern P are different. Show how to accelerate
    NAIVE-STRING-MATCHER to run in time O(n) on an n-character text.</p>
  </blockquote>
  
  <p>So I am trying to optimize the naive brute force solution I came up with, but I don't think I can do any better to reduce the overall running time to O(n).</p>
  
  <pre><code> &lt;?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&lt;$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&lt;$k; $j++){ // big O(k)
                  if($b[$j] == $a[$j])
                      $bool = true;
                  else {
                      $bool = false;
                      break;   
                  }
              }
              if($bool){
                  echo "Found at index: ".$i."&lt;br&gt;";
                  $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;
  ?&gt; 
  </code></pre>
  
  <p>I certainly reduced the running time for this particular instance, but imagine the worst case a Text with all its chars set to 'a', I will dive into the second loop each and every time which is O(k*n).</p>
  
  <p>What is the big-O of the algorithm?
  and can I get more efficient  solution?</p>