Naïve String Matching Algorithm

Naïve String Matching Algorithm

It employs a Brute Force technique to identify the presence of a pattern in the given text.

It is not efficient algorithm because it takes the time complexity of the algorithm to check for a sub string is O((m-n)n) where m is the length of the text and n is the length of the pattern (sub string) to be searched.

There is no preprocessing is required for this algorithm unlike KMP algorithm.

Preprocessing time: 0 (no preprocessing)

Matching time: O((n-m)m).

NaiveStringMatcher(text, pattern)

tLen ← length [text]

pLen ← length [pattern]

for i ← 0 to tLen - pLen do

     mCount = 0;

for j ← 0 to pLen do

    if text[i] != pattern[j+i]

        break;

    mCount++;

     if(mCount == pLen)

           return Valid match found at position : + i!!

public class NaiveStringMatch {

      public static void main(String[] args) {

            String text = "I love to work on the algorithms!";

            String pattern = "the algorithms";

            naiveStringMatcher(text, pattern);

      }

      /**

       * Implementation of Naive String matching algorithm.

       * @param text

       * @param pattern

       */

      private static void naiveStringMatcher(String text, String pattern) {

            char[] txtArr = text.toCharArray();

            char[] patArr = pattern.toCharArray();

            int tLen = txtArr.length;

            int pLen = patArr.length;

            for (int i = 0; i < tLen - pLen; i++) {

               int charMatchCount = 0;

               for (int j = 0; j < pLen; j++) {

                    /**

                     * If pattern mismatch, break next searching point.

                     **/

                     if (patArr[j] != txtArr[i + j]) {

                          break;

                     }

                     charMatchCount++;

               }

               if (charMatchCount == pLen) {

                     print("String found at "+(i+1)+" position!!");

                     break;

               }

            }

      }

      private static void print(String string) {

            System.out.println(string);

      }

}

Output:

String found at 19 position!!