## 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!!