Я думаю, что Бойер-Мур-Хорспул можно сделать быстрее с помощью этого варианта (я не знаю его имени, может быть, мое имя :-)). Алгоритм BMH не использует совпавшие символы и информацию о несоответствующих символах. Используется только последний текстовый символ в текущей позиции шаблона. Например:
В BMH следующая позиция (C выровнена со следующим C):
Text : TTTTZBCTTTTTTTTTTTTT
Pattern: ABCCABC
Text : TTTTZBCTTTTTTTTTTTTT
Pattern: ABCCABC
Если мы используем совпавшие символы, следующая позиция (BC выравнивается относительно следующего BC):
Text : TTTTZBCTTTTTTTTTTTTT
Pattern: ABCCABC
Text : TTTTZBCTTTTTTTTTTTTT
Pattern: ABCCABC
Если мы используем совпавшие символы и непропаренный символ, следующая позиция (BC выравнивается по отношению к следующему BC, но поскольку символ шаблона, который не соответствует, то есть A, совпадает с предыдущим символом следующего BC, это также не будет совпадать. Так как нет другого BC, пропускается длина шаблона):
Text : TTTTZBCTTTTTTTTTTTTT
Pattern: ABCCABC
Text : TTTTZBCTTTTTTTTTTTTT
Pattern: ABCCABC
Это реализация Java (все еще может быть улучшена), используйте на свой страх и риск, потому что я не проверил ее полностью. В моих тестах производительности Бойер-Мур-Хорспул по-прежнему побеждает эту реализацию. Но, как и ожидалось, если шаблон используется повторно (без предварительной обработки шаблона для обоих), эта реализация выигрывает.
public static int[] processPattern1(char[] pattern) {
int[] skip = new int[256];
for (int i = 0; i < skip.length; ++i) {
skip[i] = pattern.length;
}
for (int i = 0; i < pattern.length - 1; ++i) {
skip[pattern[i]] = pattern.length - i - 1;
}
return skip;
}
public static int[] processPattern2(char[] pattern) {
int[] skip = new int[pattern.length];
int i, j, k, x, y;
int lpos = pattern.length - 1;
int l2pos = pattern.length - 2;
OUTER:
for (k = l2pos; k > -1; k--) { // k points to unmatched pattern character
j = k + 1;
for (i = k; i > 0; i--) {
if (pattern[i] == pattern[j] && pattern[i-1] != pattern[k]) {
for (x = i + 1, y = j + 1; y < pattern.length && pattern[x] == pattern[y]; x++, y++) {
}
if (y == pattern.length) {
skip[k] = pattern.length - x;
continue OUTER;
}
}
}
for (x = lpos - j; x > -1; x--) {
if (pattern[x] == pattern[lpos]) {
for (i = x - 1, y = l2pos; i > -1 && pattern[i] == pattern[y]; i--, y--) {
}
if (i == -1) {
skip[k] = lpos - x;
continue OUTER;
}
}
}
skip[k] = pattern.length;
}
return skip;
}
public static int search(char[] text, char[] pattern, int[] skip1, int[] skip2) {
int k = pattern.length - 1;
int i, j;
int lpos = k;
int l2pos = pattern.length - 2;
while (k < text.length) {
if (text[k] == pattern[lpos]) {
for (j = l2pos, i = k - 1; j > -1 && text[i] == pattern[j]; j--, i--) {
}
if (j == -1) {
return i + 1;
}
k += skip2[j];
} else {
k += skip1[text[k]];
}
}
return -1;
}
public static void main(String[] args) {
String origText = "TTTTTTTTTTTTTTTZBCRABCCABCTTTTTTTTTTTTT";
char[] pattern = "ZBCRABCCABC".toCharArray();
char[] text = origText.toCharArray();
int[] skip1 = processPattern1(pattern);
int[] skip2 = processPattern2(pattern);
System.out.println(search(text, pattern, skip1, skip2) == origText.indexOf(pattern));
}