Problem:
Given a word, find the first matching index in a string.For example, given a word "needle", the first matching index in "a needle in a needleless haystack" is 2.
Solution:
class Solution {
//time worst O(MN), typical O(1.1N), space O(1)
public static int brutalForce(String pattern, String txt) {
int N = txt.length();
int M = pattern.length();
int i, j = 0;
for(i = 0; i < N - M; i++) {
for(j = 0; j < M; j++) {
if(pattern.charAt(j) != txt.charAt(i + j)) break;
}
if(j == M) return i;
}
return -1;
}
public static void main(String...args) {
String pattern = "needle";
String txt = "a well needed needle in the haystack";
String txt2 = "a stick in the haystack";
System.out.println(brutalForce(pattern, txt));
BoyerMoore bm = new BoyerMoore(pattern);
System.out.println(bm.match(txt));
System.out.println(brutalForce(pattern, txt2));
System.out.println(bm.match(txt2));
}
//time worst O(NM), typical O(N/M), space O(R)
private static class BoyerMoore{
private int[] right;
String pattern;
public BoyerMoore(String pattern) {
int R = 256;
this.pattern = pattern;
right = new int[R];
int M = pattern.length();
for(int i = 0; i < R; i++) {
right[i] = -1;
}
for(int i = 0; i < M; i++) {
right[pattern.charAt(i)] = i;
}
}
public int match(String txt) {
int N = txt.length();
int M = pattern.length();
int skip;
for(int i = 0; i < N - M; i += skip) {
skip = 0;
for(int j = M - 1; j >= 0; j--) {
if(txt.charAt(i + j) != pattern.charAt(j)) {
skip = j - right[txt.charAt(i + j)];
if(skip < 1) skip = 1;
break;
}
}
if(skip == 0) return i;
}
return -1;
}
}
}
