```
public class Solution {
public int strStr(String haystack, String needle) {
int neeLen = needle.length();
int hayLen = haystack.length();
int skip;
//pre-compute
//right is the hash for all element of needle, store its index, otherwise, it store -1
int[] right = new int[256];
for (int c = 0; c < 256; c++) {
right[c] = -1;
}
for (int i = 0; i < neeLen; i++) {
right[needle.charAt(i)] = i;
}
for (int i = 0; i <= hayLen - neeLen; i += skip) {
skip = 0;
//each loop we find there is no match, we get the index in right, and get the skip that we need to jump for the second time
for (int j = neeLen - 1; j >= 0; j--) {
if (needle.charAt(j) != haystack.charAt(i+j)) {
//make sure we move 1 step
skip = Math.max(1, j - right[haystack.charAt(i+j)]);
break;
}
}
if (skip == 0) return i;
}
return -1;
}
}
```