Информатика · объяснение и практика

Z-функция строки: длины совпадения с её началом

Z-функция без путаницы с префикс-функцией: совпадение от текущей позиции, правая граница известного блока и длина результата.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Методы алгоритмов: углубление · Учебная карта

В маршруте Сортировки и сравнение строк · 10 тем

Главная мысль

Значение Z[i] равно длине совпадения начала строки с фрагментом, начинающимся в позиции i. Сравнение останавливают на первом различии или конце строки. Здесь позиции нумеруются с нуля, а Z[0] по соглашению принимается равным нулю.

Длина относится к старту фрагмента

Для вычисления Z[i] поставьте один указатель в начало строки, другой — в позицию i. Пока символы равны, оба двигаются вправо. Число успешных совпадений и есть искомая длина. Фрагмент может продолжаться после позиции i, поэтому значение не описывает часть, заканчивающуюся на ней.

Рассмотрим строку«xyxxy». В позиции 2 начинается«xxy»: первый x совпадает с начальным x, но следующий x не совпадает с начальным y. Значит, длина равна 1. В позиции 3 начинается«xy», и оба символа совпадают с началом строки: длина равна 2.

Сохраняем уже известную правую область

Наивное посимвольное сравнение в каждой позиции может много раз повторять одну работу. Быстрый алгоритм хранит ранее найденный совпадающий блок[l,r), который заканчивается правее остальных. Внутри него символы уже сопоставлены с началом строки, поэтому часть следующего совпадения можно узнать из предыдущих значений.

Но переносить известную длину без ограничения нельзя. Если её конец выйдет за r, новые символы там ещё не проверялись. Начальное значение ограничивают расстоянием r−i, после чего при необходимости продолжают прямые сравнения. Именно различие между известной областью и неизвестным продолжением предотвращает необоснованный большой ответ.

Пример

Для «xyxxy»массив Z при принятом Z[0]=0: [0,0,1,2,0].

Z[3]=2 указывает на«xy», начинающееся с позиции 3. Это не длина суффикса, который заканчивается на позиции 3.

Как не перепутать две похожие функции

Префикс-функция выбирает совпадение, заканчивающееся в текущей позиции обработанной части. Z-функция выбирает совпадение, начинающееся в текущей позиции полной строки. Обе используют совпадение с началом, но привязывают к индексу разные границы. Поэтому одинаковые названия массива и похожая длина ответа не делают их взаимозаменяемыми.

Для проверки полезны строка без повторов, строка из одинаковых символов и случай с частичным совпадением. При поиске образца через объединённую строку нужно отдельно пересчитать индекс в координаты текста и выбрать безопасный разделитель. Условие совпадения длины образца относится к его началу в данной позиции, а не к соседней позиции или длине всего остатка.

От чтения к действию

А теперь — вы

В строке«uvuvw»из позиции 2 начинается«uvw». Каково Z[2]?

Частые вопросы

Почему Z[0] здесь не равно длине строки?

Это принятое соглашение для первого элемента. В разных описаниях его определяют иначе; остальные значения от этого не меняются.

Можно скопировать известную длину за правую границу блока?

Нет. Сначала она ограничивается концом уже проверенной области; дальнейшее совпадение надо проверить.

Углублённый разбор

Преобразование Z-массива в префикс-функцию

Z-массив и префикс-функция описывают одни совпадения с разными привязками к индексам. Из корректного Z можно восстановить π без повторного сравнения символов, заполняя каждую позицию только один раз.

Перед началом: Z-функция; Собственная граница.

Совпадающий блок создаёт кандидаты для нескольких концов

Если Z[i]=L, то s[i:i+L] совпадает с префиксом длины L. Значит для каждого j=0,…,L−1 префикс длины j+1 является суффиксом обработанной части, заканчивающейся в i+j. Это даёт кандидат π[i+j]≥j+1. Старт i>0 обеспечивает собственность границы: совпадающий префикс короче всей части до текущего конца.

Для одного конца k большую длину границы даёт меньший старт i, поскольку кандидат равен k−i+1. Поэтому обрабатываем старты i по возрастанию. Первый присвоенный ненулевой кандидат в позиции k оказывается максимальным среди всех блоков, которые туда доходят. Переписывать его более коротким значением не нужно.

Идите внутри блока справа налево и останавливайтесь на заполненном

Для каждого i проверяем j от Z[i]−1 до 0. Если π[i+j] ещё нулевая, записываем j+1. Если позиция уже заполнена, дальнейший проход по этому блоку прекращаем. Ранее обработанный блок, дошедший до этого конца, начинался левее и покрывает оставшуюся общую часть не хуже текущего. Его кандидаты там длиннее.

Хотя вложенные циклы выглядят квадратичными, каждое успешное присваивание заполняет новую позицию и происходит не больше n раз. Неуспешная проверка даёт не больше одного прекращения на каждый i. Поэтому общая работа линейна. Продолжение после уже заполненной позиции было бы корректно по максимуму, но потеряло бы эту простую оценку стоимости.

Преобразование предполагает допустимость входного массива

Алгоритм принимает Z настоящей строки с оговорённым Z[0]=0. Произвольный набор чисел в допустимых пределах не обязательно реализуется строкой. Получение некоторого π после описанного прохода не является само по себе проверкой реализуемости. Для такой задачи нужны дополнительные ограничения согласования совпадений.

В контрольном примере полезно независимо вычислить π по прямому определению границы и сравнить массив целиком. Это проверяет и начало диапазона i>0, и концы i+Z[i]−1, и правило остановки. Нельзя сверять только последний элемент: внутренние значения отвечают за последующие откаты и могут содержать незаметную ошибку.

Три совпадающих блока

Условие. Для s=abacaba и Z=[0,0,1,0,3,0,1] восстановите π описанным линейным преобразованием.

  1. При i=2 длина Z равна 1, поэтому записываем π[2]=1.
  2. При i=4 блок длины 3 заполняется справа: π[6]=3,π[5]=2,π[4]=1.
  3. При i=6 текущая позиция π[6] уже заполнена 3. Новый кандидат 1 короче, поэтому обработка этого блока прекращается.
  4. Остальные старты имеют Z=0. Получаем π=[0,0,1,0,1,2,3], где нулевые позиции означают отсутствие непустой собственной границы.

Ответ. π=[0,0,1,0,1,2,3].

Проверка. Прямые границы префиксов abac,abaca,abacab,abacaba имеют длины 0,1,2,3 соответственно. Последняя граница aba проверяется посимвольно, а весь префикс никогда не считается собственной границей.

Где легко ошибиться. Входной Z должен соответствовать какой-то строке. Линейное преобразование массивов не является автоматическим валидатором произвольного числового ввода.

Проверьте понимание

Чему равен последний элемент восстановленного π взадаче?

Вопросы к этой главе

Почему не заполнять справа по всем стартам сразу?

Порядок стартов определяет, что первый кандидат является максимальным. При обратном порядке раннее короткое присваивание могло бы помешать более длинной границе, если сохранить то же правило остановки.

Нужны ли исходные символы?

Для преобразования корректного Z — нет. Для независимой проверки учебного примера символы полезны, а для проверки реализуемости произвольного массива требуется отдельная задача.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • HPI/KIT: Competitive Programming, String Algorithms

    Первичные материалы AlgorithmEngineering/ScalableAlgorithms: вебом прочитаны определения prefix/Z, откат и поиск периода. Новые преобразования массивов, подсчёты и текстовые примеры главы выведены отдельно; OCR массивы из слайдов не переносились.

Поиск с одной заменой через прямую и обратную Z-функции

Одну замену в окне можно локализовать между точным совпадением слева и точным совпадением справа. Два Z-прохода дают эти длины для всех стартов и позволяют проверить каждое окно за постоянное дополнительное время.

Перед началом: Z-функция; Расстояние Хэмминга.

Два совпадения покрывают всё, кроме одной позиции

Пусть непустой образец P длины m сравнивается с окном T[i:i+m]. Обозначим L длину самого длинного совпадающего начала, R — конца, оба значения ограничим m. Если L=m, окно совпадает точно. Иначе первая несовпавшая позиция равна L, и не больше одной замены требуется тогда и только тогда, когда R≥m−L−1.

Равносильный компактный тест L+R≥m−1 работает и для точного совпадения. Он относится к одинаковой длине окна и образца: вставки и удаления не разрешены. Если требуется ровно одна замена, точные совпадения нужно исключить отдельно. Смешивать этот критерий с расстоянием Левенштейна нельзя.

Проверка всех окон через два точных совпадения
iОкноLRL+R≥3
0abda21да
1bdaa01нет
2daab00нет
3aabc10нет
4abca44да
5bcaa01нет
6caax00нет
7aaxc10нет
8axca12да

Обратный текст даёт суффиксное совпадение

Z для P+разделитель+T даёт L для каждого старта. Для R вычисляют Z обращённого образца и обращённого текста. Исходное окно [i,i+m) превращается в окно с началом n−i−m вобращённом T, где n — длина текста. Этот индекс относится к началу перевёрнутого окна, а не к последнему исходному символу.

Разделитель должен отсутствовать в обоих алфавитах либо быть отдельным служебным символом. Совпадения ограничивают длиной m, чтобы они не выходили за смысл образца. Два Z-массива считаются линейно по m+n, после чего остается один проход по всем n−m+1 окнам. Символы должны иметь одинаковую единицу сравнения во всех четырёх строках.

Проверка одной границы не подтверждает всю реализацию

Обычная ошибка — использовать в обратном массиве индекс n−i−1. Он указывает на один символ, но не на начало всего перевёрнутого окна. Другая ошибка — разрешить L+R≥m−2, что уже допускает две несовпавшие позиции. Поэтому полезен пример с ошибкой слева, в середине и с точным совпадением.

Для небольшого текста результат независимо проверяют прямым подсчётом разных символов в каждом окне. Этот маршрут квадратичен по размеру образца, но не использует Z и обратную индексацию. Совпадение обоих результатов проверяет именно новый способ ускорения, а не только повторяет его формулу с теми же ошибочными индексами.

Одна замена в трёх окнах

Условие. P=abca,T=abdaabcaaxca. Найдите все старты окон длины 4 с не более одной заменой, считая позиции с нуля.

  1. В позиции 0 окно abda имеет L=2 и R=1. Сумма 3=m−1, поэтому допускается одна замена d на c.
  2. В позиции 4 окно abca совпадает точно: L=R=4. Оно также входит в ответ для «не более одной».
  3. В позиции 8 окно axca имеет L=1,R=2, что снова даёт сумму 3 иоднузамену x на b.
  4. Для остальных шести стартов суммы меньше 3. Значит полный ответ{0,4,8}; непосредственное сравнение окон подтверждает числа несовпадений 1,0,1.

Ответ. Подходят старты 0,4,8.

Проверка. Обратные начала этих окон равны 8,4,0 втекстедлины 12. Прямой подсчёт Хэмминга по всем девяти окнам независимо исключает остальные старты.

Где легко ошибиться. Для обратного массива нужен старт n−i−m, а не n−i−1. Также уточняйте «ровно одна» или «не более одной»: точное совпадение различает эти запросы.

Проверьте понимание

Какие старты подходят в разобранном тексте?

Вопросы к этой главе

Что делать, если m>n?

Полных окон нет, поэтому ответ пуст. Вычислять обратные отрицательные индексы не нужно. Для пустого образца требуется отдельная договорённость о позициях и допустимых ошибках.

Почему два совпадения достаточны?

После первого несовпадения все оставшиеся позиции должны совпасть. Суффикс длины не меньше m−L−1 проверяет ровно это условие, не разрешая вторую ошибку.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • HPI/KIT: Competitive Programming, String Algorithms

    Первичные материалы AlgorithmEngineering/ScalableAlgorithms: вебом прочитаны определения prefix/Z, откат и поиск периода. Новые преобразования массивов, подсчёты и текстовые примеры главы выведены отдельно; OCR массивы из слайдов не переносились.

Зеркальные радиусы Манакера для всех палиндромных центров

Для каждого центра строки можно найти максимальный палиндром, не расширяя его с нуля. Алгоритм Манакера переносит уже известный радиус из зеркального центра внутри правого палиндромного окна. Ограничение по краю окна и отдельные соглашения для чётной и нечётной длины обеспечивают корректность и линейное время.

Перед началом: Палиндромная подстрока; Окно уже проверенного совпадения.

Два массива требуют разных определений центра

Нумеруем символы с нуля. Нечётный радиус d₁[i] включает центральный символ и описывает отрезок [i−d₁[i]+1,i+d₁[i]−1]. Он всегда не меньше единицы. Чётный радиус d₂[i] относится к центру перед i и описывает [i−d₂[i],i+d₂[i]−1]; он может быть нулевым.

Длины максимальных палиндромов равны соответственно 2d₁−1 и 2d₂. Эти соглашения фиксируют, где находятся границы и какая зеркальная позиция используется. Нельзя подставлять чётный радиус в нечётную формулу: ошибка на единицу меняет и восстановленную подстроку, и следующую итерацию алгоритма.

Радиусы для cabbaabac; чётный центр находится перед i
iсимволd₁[i]d₂[i]
0c10
1a10
2b10
3b12
4a10
5a12
6b20
7a10
8c10

Зеркало даёт только гарантированную часть радиуса

Для нечётного случая храним самый правый известный палиндром [l,r]. Если i≤r, зеркальный центр равен j=l+r−i. Начальный радиус берём min(d₁[j],r−i+1). Известная симметрия гарантирует эту часть, но за r начинается ещё не проверенная область. От полученной границы выполняем обычное расширение сравнением букв.

Если найденный палиндром выходит правее прежнего окна, заменяем [l,r] его границами. Для чётных центров зеркальный индекс равен l+r−i+1, а окно после вычисления радиуса k имеет вид [i−k,i+k−1]. Алгоритм аналогичен, но эти индексы выводятся из выбранного центра между буквами, а не запоминаются по сходству с нечётным вариантом.

Суммарные расширения двигают правую границу

Копируемые части радиусов уже доказаны и не требуют повторных успешных сравнений. Новое успешное расширение за старое окно увеличивает его правую границу; она не убывает и может пройти строку лишь один раз. Неудачных завершающих сравнений не больше постоянного числа на центр. Так оба прохода занимают O(n).

Полученные массивы содержат все максимальные центровые радиусы, но не список всех различных палиндромных слов. У одного слова могут быть разные вхождения, а внутри максимального радиуса содержатся меньшие палиндромы того же центра. Для поиска всех вхождений достаточно радиусов; для подсчёта различных значений нужна дополнительная структура или явное удаление повторов.

Два различных самых длинных палиндрома

Условие. Для строки cabbaabac найдите массивы нечётных и чётных радиусов и все подстроки максимальной длины. Используйте нулевую нумерацию.

  1. Нечётные радиусы равны (1,1,1,1,1,1,2,1,1). В центре шесть буквы a по обе стороны от b дают aba длины три.
  2. Чётные радиусы равны (0,0,0,2,0,2,0,0,0). Центр перед позицией три задаёт отрезок [1,4], то есть abba.
  3. Центр перед позицией пять задаёт отрезок [3,6], то есть baab. Оба чётных палиндрома имеют длину четыре.
  4. У первого расширение останавливается на сравнении c и a вне [1,4]. У второго внешние буквы b и a вне [3,6] также различны. Поэтому радиусы два максимальны.
  5. Максимум среди 2d₁−1 и 2d₂ равен четырём. Полный перебор всех подстрок с проверкой обращения находит ровно abba и baab как различные самые длинные значения.

Ответ. Максимальная длина равна 4; самые длинные подстроки — abba и baab. Нечётный максимум aba короче и имеет длину 3.

Проверка. Прямое сравнение каждой подстроки с её обращением независимо проверяет оба массива радиусов и полноту списка максимальных вхождений.

Где легко ошибиться. Не копируйте зеркальный радиус целиком, когда он выходит за правую границу окна. Известное зеркало удостоверяет только часть внутри уже проверенного палиндрома.

Проверьте понимание

Каков полный список различных самых длинных палиндромных подстрок cabbaabac?

Вопросы к этой главе

Почему d₁[i] хотя бы один даже у несовпадающих соседей?

Центральная буква сама является палиндромом длины один. Расширение начинается с проверки соседней пары, поэтому минимальный нечётный радиус равен единице.

Почему это отличается от Z-функции?

Z сравнивает фрагмент с началом всей строки. Здесь сравниваются симметричные буквы вокруг разных центров; зеркальный индекс и смысл окна другие, хотя идея повторного использования информации похожа.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • B. Kostka: Sports Programming in Practice, §5.1

    Прочитан §5.1 о чётных/нечётных радиусах и зеркале самого правого палиндрома. Остальные главы книги не заявляются прочитанными. Строка cabbaabac и все её радиусы независимо проверены полным перебором.

Минимальный циклический сдвиг: исключение диапазона начал

Кольцевая запись не имеет выделенного начала. Для канонического представления можно выбрать лексикографически минимальное вращение, не сортируя все сдвиги и не разбивая слово на факторы. Два кандидата сравниваются до первого различия. У проигравшего исключается сразу диапазон начал: уже известный общий префикс переносит то же доказательство невыгодности на соседние позиции.

Перед началом: Лексикографическое сравнение равнодлинных слов; Циклическая индексация по модулю длины.

Равные вращения требуют отдельного правила выбора

Непустое конечное слово над упорядоченным алфавитом; среди равных минимальных вращений выбирается наименьший индекс.

Для непустого s длины n вращение с началом i равно s[i:]s[:i]. Сравниваются ровно n символов; доступ по модулю n позволяет не создавать удвоенную копию. Если минимальное слово получается из нескольких начал, договоримся возвращать наименьший исходный индекс. Например, периодичность может дать равные вращения, а не единственного победителя.

Храним два разных начала i,j и длину k уже совпавшего префикса. Изначально i=0,j=1,k=0. Если очередные символы равны, увеличиваем k. При k=n сравниваемые вращения равны целиком, поэтому дальнейшее чтение бессмысленно. У односимвольного слова второй кандидат сразу находится за допустимым диапазоном.

Первое различие отбрасывает целый блок

Пусть после k равных символов вращение i имеет больший символ, чем вращение j. Для каждого h от 0 до k вращение с началом i+h также проигрывает вращению j+h: первые k−h символов равны, а следующее сравнение содержит ту же строгую разницу. Здесь начала свидетелей понимаются циклически. Следовательно позиции i,…,i+k не могут быть минимальными.

Продвигаем проигравший указатель на k+1, обнуляем k и продолжаем сравнение. При совпадении указателей один дополнительно увеличиваем, чтобы не сравнивать вращение с самим собой. При противоположном знаке различия симметрично продвигается j. Инвариант состоит в том, что все уже пройденные начала, кроме текущих кандидатов, исключены свидетельством меньшего вращения.

Повторный просмотр оплачивается продвижением кандидата

Каждый сброс k после различия сопровождается продвижением одного указателя как минимум на k+1. Поэтому длинная серия равных сравнений оплачивается увеличением индекса, который больше не возвращается назад. До выхода одного кандидата за n суммарное число сравнений линейно; заключительная серия равенств также содержит не больше n символов.

Алгоритм возвращает min(i,j), когда один кандидат исчерпан или два оставшихся совпали на всей длине. Для проверки полезны постоянное слово, нетривиальная степень и слово с длинным общим началом вращений. Проверка сортировкой всех вращений годится как независимый оракул коротких примеров, но не является частью линейного метода.

Два длинных совпадения исключают промежуточные начала

Условие. Найдите минимальное вращение слова bbaaccaadd при порядке a<b<c<d. Нумеруйте начала с нуля и примените метод двух кандидатов.

  1. Кандидаты 0 и 1 совпадают на b, затем сравниваются b и a. Проигрывает 0; исключаем начала 0,1 и переводим i в 2. Кандидат 1 затем проигрывает уже по первой букве b>a и переводится в 3.
  2. Начала 2 и 3 совпадают на a; далее a<c. Проигрывающий j перескакивает из 3 в 5, исключая 3 и 4. Начало 5 с буквой c затем уступает началу 2 и переходит в 6.
  3. Вращения из 2 и 6 совпадают на aa. Следующая пара равна c,d; меньше вращение из 2. Исключаем начала 6,7,8, переводим j в 9.
  4. Начало 9 имеет букву d и также проигрывает началу 2. Указатель j становится 10, то есть достигает длины слова. Остаётся начало 2 с вращением aaccaaddbb.

Ответ. Минимальное вращение — aaccaaddbb, его начало имеет индекс 2.

Проверка. Независимое построение всех десяти вращений даёт тот же минимум и единственное минимальное начало 2. Отдельные периодические тесты проверяют правило наименьшего индекса при равенстве вращений.

Где легко ошибиться. Не заканчивайте сравнение после произвольного короткого совпадения и не считайте разные начала обязательно разными словами. Кольцевое равенство проверяется на всей длине n.

Проверьте понимание

Какой индекс начала минимального вращения получен для bbaaccaadd в разобранном примере?

Вопросы к этой главе

Это тот же результат, что факторизация строки на слова Линдона?

Нет. Здесь выбирается одно начало кольцевой записи. Факторизация разбивает фиксированную линейную запись на последовательность канонических блоков; задача и возвращаемые данные различаются.

Нужен ли особый символ конца строки?

Нет. Все сравнения выполняются циклически и ограничены n символами. Добавление маркера изменило бы сам набор вращений, поэтому здесь оно не используется.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Booth — Lexicographically least circular substrings

    Авторская постановка канонического циклического представления. Описанный здесь метод двух кандидатов доказан отдельно; он не отождествляется с приведённой автором реализацией через KMP-ссылки.

Бойер—Мур: плохой символ и хороший суффикс дают разные безопасные сдвиги

После несовпадения при поиске шаблона справа налево уже известны и плохой символ текста, и совпавший суффикс шаблона. Эти сведения исключают разные ближайшие начала. Бойер—Мур использует максимум двух безопасных сдвигов: меньшие позиции уже запрещены хотя бы одним аргументом. После полного совпадения тоже нужен обоснованный сдвиг, иначе можно потерять перекрывающееся вхождение.

Перед началом: Точное вхождение шаблона в текст; Собственная граница строки и общий суффикс.

Плохой символ ограничивает ближайшее выравнивание

Поиск непустого точного шаблона, сравнение справа налево, индексы с нуля; ищутся все вхождения, включая перекрывающиеся.

Пусть шаблон P длины m начинается в тексте на s, а несовпадение найдено на индексе j. Обозначим c=T[s+j], last(c) — самое правое вхождение c в P либо −1, если его нет. Безопасный сдвиг равен max(1,j−last(c)). При меньшем положительном сдвиге плохой символ оказался бы правее любого подходящего ему символа шаблона.

Если правое вхождение c находится правее j, выражение j−last(c) неположительно и правило даёт только единицу. Это консервативный вариант с одной позицией на символ. Расширенная таблица может искать подходящее вхождение строго левее j, но нельзя незаметно смешивать определения таблиц и формулу сдвига.

Хороший суффикс сохраняет уже совпавшие буквы

Суффикс P[j+1:] уже совпал с текстом. Ищем ближайшее положительное смещение, при котором перекрывающаяся часть этого суффикса согласуется с новым шаблоном. Если перед его новым полным вхождением стоит тот же символ P[j], такой вариант также исключён: он повторил бы известное несовпадение. Это сильное правило хорошего суффикса.

Если внутреннего подходящего вхождения нет, сохраняем максимально длинную часть суффикса, совпадающую с префиксом P. При пустом совпавшем суффиксе достаточно сдвига 1. Таблицы длин совпадающих суффиксов можно получить из Z-функции обращённого шаблона; геометрия выравнивания объясняет, что именно должна означать запись таблицы.

Максимум правил и отдельный случай полного совпадения

Каждый из двух аргументов доказывает отсутствие вхождения на всех меньших положительных смещениях. Поэтому их максимум безопасен; складывать значения нельзя, поскольку доказательства могут запрещать одни и те же позиции. Конкретное большее значение зависит и от символа текста, и от структуры шаблона.

После полного совпадения сдвигаемся на m−b, где b — длина наибольшей собственной границы P. Это сохраняет ближайшее возможное перекрытие. Сдвиг сразу на m пропустит ответы у шаблона с ненулевой границей. Простая реализация без дополнительного учёта уже проверенных участков не получает универсальную линейную оценку только из наличия двух таблиц.

Сначала выигрывает символ, затем суффикс

Условие. Найдите все вхождения P=abacab в T=xxxxxxzzababacabacab. Используйте обычную таблицу last и сильное правило хорошего суффикса; индексы начинаются с нуля.

  1. При s=0 последнее сравнение даёт b против x. Символа x в P нет: плохой символ предлагает 5−(−1)=6, пустой суффикс предлагает 1. Сдвигаемся на 6.
  2. При s=6 окно равно zzabab. Суффикс ab совпал, а на j=3 стоят c и b. Плохой символ даёт max(1,3−5)=1. Предыдущее ab начинается в P на 0, поэтому хороший суффикс даёт сдвиг 4.
  3. В s=10 шаблон совпадает полностью. Его наибольшая собственная граница — ab длины 2, поэтому следующий сдвиг равен 6−2=4.
  4. В s=14 также получаем полное совпадение. Оба вхождения перекрываются на ab. Следующее начало 18 уже не вмещает шестисимвольный шаблон, и поиск заканчивается.

Ответ. Все вхождения начинаются в позициях 10 и 14. Сдвиги просмотренных выравниваний равны 6,4,4,4.

Проверка. Независимый перебор каждого допустимого начала текста находит ровно 10 и 14. На промежутке между 6 и 10 каждый меньший сдвиг нарушает уже совпавший суффикс; после 10 сдвиг 6 действительно потерял бы вхождение 14.

Где легко ошибиться. Не складывайте сдвиги плохого символа и хорошего суффикса. Каждый является нижней границей ближайшего ещё возможного начала; совместное ограничение задаётся максимумом.

Проверьте понимание

Какой сдвиг выбирается после несовпадения в окне zzabab при s=6 в разобранном примере?

Вопросы к этой главе

Почему после совпадения нельзя всегда сдвигаться на длину шаблона?

Ненулевая собственная граница допускает перекрытие. У abacab граница ab оставляет следующее начало через четыре символа, хотя длина шаблона равна шести.

Почему таблица последнего вхождения иногда почти не помогает?

Если плохой символ встречается правее позиции несовпадения, обычная формула даёт только единицу. Уже совпавший суффикс при этом может обосновать существенно больший сдвиг.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Tufts — Boyer-Moore, правила сдвига

    Сильное правило хорошего суффикса, плохой символ и получение суффиксных таблиц из Z обращённого шаблона. Текст, трасса и проверка всех начал вычислены отдельно.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться