title: brute force string pattern matching average analysis
body: <p>I have brute force string pattern searching algorithms as  below:</p>
  
  <pre><code>public static int brute(String text,String pattern) {
   int n = text.length();    // n is length of text.
   int m = pattern.length(); // m is length of pattern
   int j;
   for(int i=0; i &lt;= (n-m); i++) {
      j = 0;
      while ((j &lt; m) &amp;&amp; (text.charAt(i+j) == pattern.charAt(j)) ) {
         j++;
      }
      if (j == m)
       return i;   // match at i
    }
    return -1; // no match
  } // end of brute()
  </code></pre>
  
  <p>While anlaysising above algorithm here author mentioned worst case and average case.</p>
  
  <p>I undertstood worst case scenario performance but for average <strong>how author came with O(m+n) performance? Need help here.</strong></p>
  
  <p>Brute force pattern matching runs in time O(mn) in the worst case.</p>
  
  <p>Average for most searches of ordinary text take O(m+n), which is very quick.  </p>
  
  <p>Example of a more average case:
  T: "a string searching example is standard"
  P: "store"</p>
  
  <p>Thanks for your time and help</p>