Saturday 22 April 2017

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 substring is O((m-n)n) where m is the length of the text and n is the length of the pattern (substring) 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).

Pseudo Code:
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!!

Implementation:
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!!

1 comment:

Related Posts Plugin for WordPress, Blogger...