All About Programming

Using prefix information to do better than brute force algorithm Recall the brute-force algorithm: n = T.length(); m = P.length(); i0 = 0; // Line P up with the first character of T i = 0; // Start matching with first char in T j = 0; // Start matching with first char in P while ( i < n ) // Not all characters used { if ( T[i] == P[j] ) { /* =============================================== T[i] and P[j] match ==> try next pair =============================================== */ i++; // Match next pair j++; if ( j == m ) return ( i0 );

Read full article from