Sunday 15 September 2013

Naive Pattern Searching Algorithm

class StringMatchingAlgorithms{
static boolean isFoundHelper(char[] target, char[] pattern){
int targetLen = target.length;
int patternLen = pattern.length;
int k,l;
for(int i = 0; i < targetLen-patternLen+1; i++){
k = 0;l = i;
for(int j = 0; j < patternLen; j++){
if(target[l] == pattern[j]){
k++;l++;
                          }else
break;
}
if(k == patternLen)  //Pattern found, return true
                           return true;
}
return false;
}

static boolean isFound(String s, String p){
return isFoundHelper(s.toCharArray(), p.toCharArray());
}

public static void main(String []args){
String source = "abcdefab";
String pattern = "cde";

System.out.println("Result : "+isFound(source, pattern));
}
}

Time Complexity : O(N^2)
Space Complexity : O(1)

No comments:

Post a Comment