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