Ответ 1
Сначала я использую p[i] символ в шаблоне, m длину шаблона, $ последний символ в шаблоне, т.е. $ = p[m-1].
Существует два сценария для случая эвристики хорошего суффикса 1.
Ситуация 1
Рассмотрим следующий пример:
leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
cXXXbXXXcXXXcXXX
^
| mismatch here
Таким образом, подстрока XXX в шаблоне cXXXbXXXcXXXcXXX является хорошим суффиксом. Несоответствие происходит при значении c. Поэтому после несоответствия нам следует сдвинуть 4 вправо или 8?
Если мы сдвинем 4, как в следующем, то снова будет повторяться тот же самый несоответствие (b mismathes c),
leading TEXT cXXXbXXXcXXXcXXX rest of the TEXT
cXXXbXXXcXXXcXXX
^
| mismatch occurs here again
Таким образом, в этой ситуации мы можем сдвинуть 8 символов вправо.
Ситуация 2
Посмотрим на другой пример
leading TEXT cXXXcXXXbXXXcXXX rest of the TEXT
cXXXXcXXXbXXXcXXX
^
| mismatch happens here
Можно ли переместить 4 или 8 или более? Очевидно, что если мы сдвинем 8 или более, мы упустим возможность сопоставить шаблон с текстом. Поэтому в этой ситуации мы можем сдвигать только 4 символа вправо.
В чем разница между этими двумя ситуациями?
Разница в том, что в первом случае несогласованный символ c плюс хороший суффикс XXX, который равен cXXX, совпадает с следующим (счетчик справа) для XXX plus характер до этого. В то время как во второй ситуации cXXX не совпадает с следующим совпадением (счетчик справа) плюс символ перед этим совпадением.
Итак, для любого данного GOOD SUFFIX (назовем его XXX) нам нужно выяснить смещение в этих двух ситуациях: (1) символ (назовем его c) до GOOD SUFFIX плюс GOOD SUFFIX, в шаблоне также соответствует следующему (счету справа) совпадению хорошего суффикса + персонажу перед ним, (2) символ плюс GOOD SUFFIX не соответствует
Для ситуации (1), например, если у вас есть шаблон, 0XXXcXXXcXXXcXXXcXXXcXXX, если после первого теста c не удастся, вы можете сдвинуть 20 символов вправо и выровнять 0XXX с текстом который был протестирован.
Так вычисляется число 20,
1 2
012345678901234567890123
0XXXcXXXcXXXcXXXcXXXcXXX
^ ^
Позиция, в которой происходит несоответствие, равна 20, сдвинутая подстрока 0XXX займет позицию от 20 до 23. И 0XXX начинается с позиции 0, поэтому 20 - 0 = 20.
Для ситуации (2), как в этом примере, 0XXXaXXXbXXXcXXX, если после первого теста c не удастся, вы можете сдвинуть только 4 символа вправо и выровнять bXXX с текстом, который был протестирован.
Так вычисляется число 4,
0123456789012345
0XXXaXXXbXXXcXXX
Позиция, в которой происходит несоответствие, равна 12, следующая подстрока, которая занимает это место, равна bXXX, которая начинается с позиции 8, 12 - 8 = 4. Если мы установим j = 12 и i = 8, тогда сдвиг j - i, что в коде <<234 > .
Граница
Чтобы рассмотреть весь хороший суффикс, нам сначала нужно понять, что такое так называемый border.
Граница - это подстрока, которая является префиксом proper и суффиксом proper строки. Например, для строки XXXcXXX, X является границей, XX является границей, XXX тоже. Но XXXc нет. Нам нужно определить начальную точку самой широкой границы суффикса шаблона, и эта информация сохраняется в массиве f[i].
Как определить f[i]?
Предположим, что мы знаем f[i] = j и для всех остальных f[k] с i < k < m, что означает самую широкую границу для суффикса, начиная с позиции i, начатого в позиции j. Мы хотим найти f[i-1] на основе f[i].
Например, для шаблона aabbccaacc в postion i=4 суффикс ccaacc, а самая широкая граница для него - cc (p[8]p[9]), поэтому j = f[i=4] = 8. И теперь мы хотим знать f[i-1] = f[3] на основе информации, которую мы имеем для f[4], f[5],... Для f[3] суффикс теперь равен bccaacc. В позиции j-1=7 это a!= p[4-1], который равен b. Таким образом, bcc не является границей.
Мы знаем, что любая граница с шириной >= 1 из bccaacc должна начинаться с b плюс граница суффикса, начиная с positin j = 8, которая в этом примере cc. cc имеет самую широкую границу c в позиции j = f[8], которая 9. Поэтому мы продолжаем поиск с сравнения p[4-1] с p[j-1]. И они снова не равны. Теперь суффикс p[9] = c, и он имеет только границу с нулевой длиной в позиции 10. поэтому теперь j = f[9] и это 10. Таким образом, мы продолжаем поиск при сравнении p[4-1] с p[j-1], они не равны и это конец строки. Тогда f[3] имеет только границу с нулевой длиной, которая делает ее равной 10.
Чтобы описать процесс в более общем смысле
Следовательно, f[i] = j означает что-то вроде этого,
Position: 012345 i-1 i j - 1 j m
pattern: abcdef ... @ x ... ? x ... $
Если символ @, который в позиции i - 1 совпадает с символом ? в позиции j - 1, мы знаем, что
f[i - 1] = j - 1; или --i; --j; f[i] = j;. Граница - это суффикс @x ... $, начиная с позиции j-1.
Но если символ @, который в положении i - 1 отличается от символа ? в позиции j - 1,
мы должны продолжить поиск справа. Мы знаем два факта: (1) мы знаем, что ширина границы должна быть меньше той, которая начиналась с позиции j, т.е. Меньше x...$. Во-вторых, граница должна начинаться с @... и заканчивается символом $, или она может быть пустой.
Исходя из этих двух фактов, мы продолжаем наш поиск в подстроке x ... $ (от позиции j до m) для границы, начинающейся с X. Затем следующая граница должна быть в j, которая равна f[j];, т.е. j = f[j];. Затем мы сравниваем символ @ с символом до X, который находится на j-1. Если они равны, мы обнаружили границу, если нет, продолжаем процесс до j > m. Этот процесс показан следующим кодом:
while (j<=m && p[i-1]!=p[j-1])
{
j=f[j];
}
i--; j--;
f[i]=j;
Теперь рассмотрим условие p[i -1] != p [j-1] , this is what we talked about in situation (2), p [i] matches p [j] , but p [i -1]!= p[j-1], поэтому мы переходим от i до j, то есть s[j] = j - i;.
Теперь единственное, что не объяснено, - это тест if (s[j] == 0), который будет иметь место, когда более короткий суффикс имеет одинаковую границу. Например, у вас есть шаблон
012345678
addbddcdd
Когда вы вычисляете f[i - 1] и i = 4, вы установите s[7]. Но когда вы вычисляете f[i-1] для i = 1, вы снова установите s[7], если у вас нет теста if (s[j] == 0). Это означает, что если у вас есть несоответствие в позиции 6, вы сдвигаете 3 вправо (выровняйте bdd в позиции cdd заняты) не 6 (не сдвигайте до add в позиции cdd занято).
Комментарии для кода
void bmPreprocess1()
{
// initial condition, set f[m] = m+1;
int i=m, j=m+1;
f[i]=j;
// calculate f[i], s[j] from i = m to 0.
while (i>0)
{
// at this line, we know f[i], f[i+1], ... f[m].
while (j<=m && p[i-1]!=p[j-1]) // calculate the value of f[i-1] and save it to j-1
{
if (s[j]==0) s[j]=j-i; // if s[j] is not occupied, set it.
j=f[j]; // get the start position of the border of suffix p[j] ... p[m-1]
}
// assign j-1 to f[i-1]
i--; j--;
f[i]=j;
}
}