Я пытаюсь обвести голову вокруг алгоритма Bitap, но мне трудно понять причины шагов алгоритма.
Я понимаю основную предпосылку алгоритма, который (исправьте меня, если я ошибаюсь):
Two strings: PATTERN (the desired string)
TEXT (the String to be perused for the presence of PATTERN)
Two indices: i (currently processing index in PATTERN), 1 <= i < PATTERN.SIZE
j (arbitrary index in TEXT)
Match state S(x): S(PATTERN(i)) = S(PATTERN(i-1)) && PATTERN[i] == TEXT[j], S(0) = 1
В английских терминах PATTERN.substring(0,i)
соответствует подстроке TEXT, если предыдущая подстрока PATTERN.substring(0, i-1)
была успешно сопоставлена, а символ в PATTERN[i]
совпадает с символом в TEXT[j]
.
То, что я не понимаю, - это битовая реализация этого. Официальная статья, подробно описывающая этот алгоритм, в основном излагает это, но я не могу представить, что должно продолжаться. Спецификация алгоритма - это только первые 2 страницы бумаги, но я выделим важные части:
Вот версия с битрейтом:
Здесь T [текст] для строки поиска:
И вот след алгоритма.
В частности, я не понимаю, что означает таблица T, и причина OR
записи в нее с текущим состоянием.
Буду признателен, если кто-нибудь поможет мне понять, что именно происходит