public class BruteForce {
static int bruteForce(String source, String target) {
int N = source.length();
int M = target.length();
for(int i = 0; i <= N - M; i++) {
int j;
for(j = 0; j < M; j++) {
if(source.charAt(i + j) != target.charAt(j)) {
break;
}
}
if(j == M) {
return i;
}
}
return -1;
}
public static void main(String...args) {
//best case, the match is found at beginning,
//worst case, the match is located at end or not in the string
String hay = "search a needle in a haystack.";
String needle = "needle";
//java String.contains method use brute force
System.out.println(hay.contains(needle));
System.out.println(hay.contains("noneedle"));
output(bruteForce(hay, needle));
output(bruteForce(hay, "noneedle"));
//modified java default implementation
output(bruteForce1(hay, needle));
output(bruteForce1(hay, "noneedle"));
}
static void output(int match) {
System.out.println(match);
if(match > 0)
System.out.println("Y");
else
System.out.println("N");
}
//java contains() implementation
static int bruteForce1(String source, String target) {
int N = source.length();
int M = target.length();
char first = target.charAt(0);
int max = N - M;
for (int i = 0; i <= max; i++) {
/* Look for first character. */
if (source.charAt(i) != first) {
while (++i <= max && source.charAt(i) != first);
}
/* Found first character, now look at the rest of v2 */
if (i <= max) {
int j = i + 1;
int end = j + M - 1;
for (int k = 1; j < end && source.charAt(j)
== target.charAt(k); j++, k++);
if (j == end) {
/* Found whole string. */
return i;
}
}
}
return -1;
}
}
