brute force string pattern matching average analysis

Question

I have brute force string pattern searching algorithms as below:

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 <= (n-m); i++) {
    j = 0;
    while ((j < m) && (text.charAt(i+j) == pattern.charAt(j)) ) {
       j++;
    }
    if (j == m)
     return i;   // match at i
  }
  return -1; // no match
} // end of brute()

While anlaysising above algorithm here author mentioned worst case and average case.

I undertstood worst case scenario performance but for average how author came with O(m+n) performance? Need help here.

Brute force pattern matching runs in time O(mn) in the worst case.

Average for most searches of ordinary text take O(m+n), which is very quick.

Example of a more average case: T: "a string searching example is standard" P: "store"

Thanks for your time and help

Answer 1

What he's referring to with the O(m+n) is the partial matches that would happen in the normal case.

For example, with your normal case you will get:

T: "a string searching example is standard" 
P: "store"

iterations:

 O(38 + 5) == 43
 a -     no match (1)
 space - no match (2)
     s     - match (3)
     t     - match (4)
     r     - no match (5)
 t     - no match (6)
 r     - no match (7)
 i     - no match (8)
 n     - no match (9)
 g     - no match (10)
 space     - no match (11)

etc...

I indented the inner loop to make it easier to understand.

Eventually you've checked all of m which is O(m), but the partial matches mean that you have either checked all of n which is O(n)(found a complete match), or at least enough charactors to equal the amount of charactors in n (partial matches only).

Overall this leads to an O(m+n) time on average.

Best case would be O(n) if the match is at the very beginning of m.