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