Intuition :
从右到左对照pattern扫描字符
当发现一个不在pattern里面的字符的时候，尽可能多的跳过字符。
Case 1：
当前匹配失败的字符不在pattern里面的时候，跳过这个字符，在右侧从下一个字符开始重新开始匹配pattern。
before
Txt · · · · · T L E
Pat · · N E E D L E
after
Txt · · · · · T L E
Pat · · · · · · N E E D L E
Case 2a:
当前匹配失败的字符在pattern里面的时候，将pattern移到与该字符对应的位置重新开始
before
Txt · · · · · N L E
Pat · · N E E D L E
after
Txt · · · · · N L E
Pat · · · · · N E E D L E
Case 2b:
当前匹配失败的字符在pattern里面，但是需要back-up，此时back-up并没有帮助。
before
Txt · · · · · E L E
Pat · · N E E D L E
Wrong
Txt · · · · · E L E
Pat N E E D L E
那么如何skip :
预先计算txt里面每个字符c在pattern里面的位置（-1表示字符不在pattern里面）
right = new int[R];
for (int c = 0; c < R; i++) {
right[c] = -1;
}
for (int j = 0; j < M; j++) {
right[pat.charAt(j)] = j;
}
Boyer-moore算法
public int search(String txt) {
int N = txt.length();
int M = pat.length();
int skip;
for (int i = 0; i < N; i += skip) {
skip = 0;
for (int j = M - 1; j >= 0; j--) {
if (pat.chatAt(j) != txt.charAt(i + j)) {
skip = Math.max(1, j - right[txt.charAt(i + j)]);
}
}
if (skip == 0) {
return i;
}
}
return N;
}