Информатика · объяснение и практика
Префикс-функция: как искать границу совпавшего фрагмента
Префикс-функция строки: собственная граница, суффикс обработанного префикса и переход к более короткому совпадению.

В теме Методы алгоритмов: углубление · Учебная карта
В маршруте Сортировки и сравнение строк · 10 тем
Главная мысль
Префикс-функция π[i] хранит длину наибольшего собственного префикса строки s[0…i], который одновременно является её суффиксом. Слово «собственный» исключает всю обработанную строку целиком. Позиции здесь начинаются с нуля, поэтому π[0]=0.
Что именно совпадает в одной позиции
Для каждой позиции рассматривают часть строки от начала до этой позиции включительно. Затем ищут её начало и конец одинаковой длины. Они должны совпасть посимвольно, а выбранная длина обязана быть меньше длины всей рассматриваемой части. Такое совпадение называют границей строки.
Префикс-функция не сообщает длину произвольного повтора где угодно внутри текста. Совпавший фрагмент обязательно начинается с начала всей строки и заканчивается в текущей позиции. Если это условие забыть, можно принять внутреннее повторение за подходящую границу и получить неверное значение.
Проверяем собственную строку
Для строки «abacabab»значения равны 0,0,1,0,1,2,3,2. Перед последним символом обработана часть«abacaba», у которой граница«aba»длины 3. Новый символ b не продолжает её до«abac», потому что следующий ожидаемый символ c.
Нужно перейти к более короткой границе самой«aba»: это«a»длины 1. Теперь следующий ожидаемый символ b совпадает с новым b, и получается граница«ab»длины 2. Переход не перебирает все предыдущие символы заново, а использует уже рассчитанное значение π для конца прежней границы.
Пример
Для «abacabab»последнее значение π равно 2: начало«ab»совпадает с концом«ab». Граница длины 4 не подходит:«abac»не равно«abab».
После неудачного продолжения границы длины 3 алгоритм переходит к её собственной границе длины 1, затем успешно добавляет новый символ.
Зачем хранить цепочку границ
При несовпадении используют переход j=π[j−1], пока не найдётся продолжение или длина не станет нулевой. Просто уменьшать j на единицу недостаточно эффективно и не отражает смысл допустимых кандидатов: следующая граница должна сама быть границей уже совпавшего фрагмента.
Это свойство помогает искать образец в длинном тексте без возврата по текстовым символам. Однако вычисление массива и организация поиска — два связанных, но разных шага. При объединении образца и текста разделитель должен отсутствовать в обоих, иначе совпадение способно перейти через границу. Единица символа и правила регистра также должны быть одинаковыми во всей процедуре.
От чтения к действию
А теперь — вы
Частые вопросы
Почему нельзя взять всю строку как её собственную границу?
Префикс должен быть собственным, то есть короче всей рассматриваемой части. Иначе ответ всегда совпадал бы с её длиной.
Префикс-функция равна Z-функции?
Нет. Префикс-функция описывает совпадение, заканчивающееся в позиции; Z-функция — начинающееся в позиции.
Углублённый разбор
Граница строки, период и полная степень
Длинная граница строки задаёт короткий период, но период не обязан делить полную длину. Отдельная проверка делимости отличает частично оборванное повторение от точной степени меньшего слова.
Перед началом: Граница строки; Префикс-функция.
Период является равенством сдвинутых участков
Число p,1≤p≤n, является периодом строки s, если s[i]=s[i−p] для всех i≥p. Это равносильно совпадению префикса длины n−p с суффиксом той же длины. Поэтому наименьший период равен n−π[n−1], где π[n−1] — длина самой длинной собственной границы. Чем длиннее граница, тем меньший сдвиг нужен.
Период p=n всегда допустим: проверяемых пар тогда нет. Если граница нулевая, меньшего периода не существует. При p<n последний повторяющийся блок может быть неполным. Определение сравнивает лишь существующие позиции и не требует добавить недостающие символы после конца строки.
Полная степень требует целого числа блоков
Если p делит n, строка состоит ровно из n/p копий своего префикса длины p. Если p не делит n, минимальный период не образует целого разбиения. Более длинный период тоже не может неожиданно дать нетривиальную полную степень: при представлении s=Tᵏ,k≥2, кратчайший период обязан делить|T|.
Для последнего факта возьмём q=|T| и минимальный p≤q. Двух копий T достаточно, чтобы сравнение со сдвигом p прошло для каждой позиции одного блока с циклическим возвратом по модулю q. Блок инвариантен такому сдвигу, значит имеет период gcd(p,q). Минимальность p вынуждает gcd(p,q)=p, откуда p|q и p|n. Это обосновывает тест делимости, а не только наблюдение примеров.
Период и граница измеряются в разных направлениях
Префикс-функция возвращает длину совпадающих краёв, а не сам период. Поэтому число π[n−1] нельзя подставлять как длину повторяющего блока. Также не следует искать период только среди делителей n, если вопрос допускает неполный последний блок. Это разные поисковые задачи с разными множествами кандидатов.
Независимый контроль малого примера перебирает все сдвиги p и проверяет равенства символов. Для проверки полной степени отдельно перебирают делители длины и сравнивают повторённый блок со всей строкой. Оба маршрута дают простые свидетельства и обнаруживают ошибку вычитания n−π либо пропущенную проверку остатка.
Один период, разные полные длины
Условие. Сравните cabcabca и cabcabcab. Найдите минимальные периоды и определите, являются ли строки нетривиальными степенями меньшего слова.
- Первая строка длины 8 имеетграницу cabca длины 5, поэтому минимальный период 8−5=3.
- Но 3 не делит 8. Строка заканчивается неполным блоком ca и не является полной нетривиальной степенью.
- Вторая строка длины 9 имеетграницу cabcab длины 6. Её минимальный период также 3.
- Теперь 9 делитсяна 3, и строка равна(cab)³. Период одинаков, но статус полного повторения различается.
Ответ. Минимальный период обеих строк 3; только cabcabcab является полной степенью(cab)³.
Проверка. Сдвиги 1 и 2 нарушают сравнение уже в начале; сдвиг 3 согласует все оставшиеся позиции. Проверка делителей 8 отдельно исключает блоки длин 1,2,4 для первой строки.
Где легко ошибиться. Минимальный период конечной строки не обязательно делит её длину. Для разложения на равные целые блоки нужна дополнительная делимость, а граница сама по себе является длиной совпадающих краёв.
Проверьте понимание
Вопросы к этой главе
Что означает период, равный длине?
Это допустимый тривиальный сдвиг без сравниваемых пар. Он не даёт нетривиального повторения и возникает как минимальный при отсутствии собственных непустых границ.
Можно использовать Z вместо π?
Да, период p проверяется условием Z[p]≥n−p. Но для поиска минимального периода по уже вычисленной π достаточно одного вычитания; выбор массива определяется имеющимися данными.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- HPI/KIT: Competitive Programming, String Algorithms
Первичные материалы AlgorithmEngineering/ScalableAlgorithms: вебом прочитаны определения prefix/Z, откат и поиск периода. Новые преобразования массивов, подсчёты и текстовые примеры главы выведены отдельно; OCR массивы из слайдов не переносились.
Подсчёт вхождений префиксов через дерево границ
Цепочка границ позволяет сосчитать вхождения каждого префикса сразу. Счётчики передаются от длинных границ к коротким, поэтому пересекающиеся вхождения учитываются без отдельного поиска каждого образца.
Перед началом: Префикс-функция; Дерево границ.
Каждый конец хранит цепочку подходящих длин
Для префикса, заканчивающегося в позиции i, значение π[i] указывает самую длинную собственную границу. Все остальные её длины получаются повторными переходами k→π[k−1]. Каждая такая длина означает вхождение соответствующего начального фрагмента, оканчивающееся в i. Разные концы дают разные вхождения, даже когда они перекрываются по символам.
Перебирать всю цепочку отдельно для каждого i может быть дорого. Вместо этого сначала увеличивают счётчик cnt[π[i]] для каждого конца. Так каждому концу назначают одну ближайшую границу, а остальные получат тот же вклад через передачу по дереву. Нулевая длина является служебным корнем, если пустой префикс не входит в вопрос.
Передавайте накопленное от большей длины к меньшей
Для k от n до 1 прибавляют cnt[k] к cnt[π[k−1]]. Переход всегда ведёт к меньшей длине, поэтому обратный порядок гарантирует, что все потомки уже передали свои вклады. Это обычное суммирование поддеревьев на дереве границ, записанное без явного построения списков детей.
В конце для каждой непустой длины добавляют единицу за сам префикс, начинающийся в позиции 0. До этого учитывались его появления как собственной границы более длинного обработанного префикса. Без последней единицы полный префикс длины n получил бы ноль, хотя он явно встречается в самой строке один раз.
Счёт зависит от понятия вхождения
Здесь вхождения допускают перекрытия. Например, фрагменты, начинающиеся через два символа, могут использовать общий символ. Если задача требует непересекающегося размещения, одних этих счётчиков недостаточно: нужен иной отбор позиций. Число всех вхождений и максимальное число непересекающихся являются разными величинами.
Для проверки полезно прямо сравнить каждый префикс с каждым допустимым окном короткой строки. Такой медленный маршрут не используется в основном алгоритме, но независимо проверяет итоговый набор чисел. Сложность передачи счётчиков после вычисления π линейна, а сами количества не превосходят числа допустимых концов строки для каждой длины.
Все начальные образцы одной строки
Условие. Для s=ababa найдите число вхождений каждого непустого префикса, разрешая перекрытия.
- Префикс-функция равна[0,0,1,2,3]. Начальные счётчики собственных границ дают cnt[1]=1,cnt[2]=1,cnt[3]=1.
- Передача от длины 3 к π[2]=1 увеличивает cnt[1] до 2. Длина 2 передаёт свой вклад служебному нулю; остальные передачи не меняют нужные положительные счётчики.
- После добавления собственного начального вхождения получаем для длин 1,…,5 значения[3,2,2,1,1].
- Например, aba встречается в позициях 0 и 2. Эти вхождения перекрываются, но имеют разные начала и оба входят в выбранное определение.
Ответ. Числа вхождений префиксов a,ab,aba,abab,ababa равны 3,2,2,1,1.
Проверка. Прямое перечисление начал даёт для a позиции 0,2,4; для ab и aba —0,2; для двух длинных префиксов только позицию 0. Все пять счётчиков совпадают.
Где легко ошибиться. После передачи по границам не забудьте собственное начальное вхождение каждого префикса. Иначе самый длинный префикс исчезнет из результата, а остальные значения будут занижены на единицу.
Проверьте понимание
Вопросы к этой главе
Почему хватает обработки длин по убыванию?
Каждая граница короче исходного префикса. Поэтому рёбра дерева строго уменьшают длину, и убывающий проход является корректным порядком накопления всех потомков.
Нужно ли учитывать пустую строку?
Только если это прямо требуется. У пустого образца принято другое число позиций, обычно n+1. В данной задаче длина 0 используется служебно и не является одним из выводимых префиксов.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- HPI/KIT: Competitive Programming, String Algorithms
Первичные материалы AlgorithmEngineering/ScalableAlgorithms: вебом прочитаны определения prefix/Z, откат и поиск периода. Новые преобразования массивов, подсчёты и текстовые примеры главы выведены отдельно; OCR массивы из слайдов не переносились.
Битовый Shift-And хранит все совпавшие префиксы
Shift-And одновременно хранит все префиксы образца, совпавшие с концом прочитанного текста. Биты реализуют параллельный переход небольшого недетерминированного автомата. Поэтому перекрывающиеся вхождения обнаруживаются без сброса и без повторного просмотра уже прочитанных символов.
Перед началом: Битовая маска; Префикс строки.
Один бит отвечает за одну длину совпадения
Пусть непустой образец P имеет длину m. Бит i состояния D равен 1 тогда и только тогда, когда префикс P[0:i+1) совпадает с суффиксом уже прочитанного текста длины i+1. Младший бит отвечает за один символ, старший значимый бит m−1 — за полное вхождение. Несколько единиц могут одновременно означать разные допустимые длины; хранить только максимальную здесь не требуется.
Для каждой буквы c предвычислим маску B[c], где бит i установлен при P[i]=c. Переход после чтения c задаётся D=((D<<1)|1)&B[c]. Сдвиг продолжает каждое прежнее совпадение на одну позицию, OR1 разрешает начать новое с текущего символа, AND удаляет все длины, которым буква c не соответствует. Буква вне образца имеет нулевую маску и обнуляет состояние.
Инвариант доказывается для каждого бита отдельно
Для i>0 новый бит существует ровно тогда, когда прежний i−1 был установлен и P[i]=c. Это и есть посимвольное условие продолжения соответствующего префикса. Для i=0 прежнее состояние не нужно: достаточна буква P[0]=c, что обеспечивает добавленная единица. Индукция по тексту даёт все совпавшие префиксы, включая те, что начинаются внутри предыдущего полного вхождения.
Если после обработки индекса j установлен бит m−1, сообщаем старт j−m+1. Затем продолжаем тем же состоянием: сброс потерял бы перекрытия. Пустой образец требует отдельного соглашения о совпадении между символами и здесь исключён. В машинном коде также нужно различать логические операции над булевыми значениями и побитовые операции над всеми разрядами.
Параллелизм ограничен шириной слова
При m≤w состояние и маски помещаются в одно w-битное слово, и каждый символ обрабатывается постоянным числом операций. Для длинного образца нужны несколько слов с переносом между ними; стоимость становится O(|T|ceil(m/w)), а не безусловно линейной с той же константой. Неограниченные целые Python удобны для прототипа, но их сдвиг и AND также зависят от числа разрядов. Битовое представление меняет организацию вычисления, не отменяя реальную стоимость памяти.
Два старта при цепочке одинаковых букв
Условие. Найдите все вхождения P=aab в T=aaabaab. Используйте три бита и нумерацию стартов с0.
- Маски равны B[a]=011₂ и B[b]=100₂, начальное D=000₂. После первых двух a состояния равны 001₂ и011₂.
- Третья a сохраняет 011₂: существуют совпавшие префиксы a и aa, начинающиеся в разных местах. Затем b даёт 100₂, полный образец заканчивается на индексе 3 и начинается в1.
- Следующие a,a дают 001₂,011₂. Последняя b снова даёт 100₂, окончание имеет индекс 6, старт 4.
- Итак, состояния по семи буквам:001,011,011,100,001,011,100. Два окна T[1:4) и T[4:7) равны aab, остальные окна не совпадают.
Ответ. Все старты равны 1 и4.
Проверка. Независимое сравнение пяти окон длины 3 даёт ровно эти два старта. На каждом шаге проверены все три бита прямым сравнением префикса образца и суффикса прочитанного текста.
Где легко ошибиться. Не заменяйте побитовое OR логическим и не сбрасывайте D после найденного вхождения. Биты описывают одновременно несколько префиксов, а не одно состояние длины.
Проверьте понимание
Вопросы к этой главе
Почему после третьей a состояние не растёт до111?
Маска буквы a равна 011 и снимает старший бит, потому что последняя буква образца — b. Совпадение aa сохраняется, но полного aab пока нет.
Почему полезна добавка OR1 на каждом шаге?
Она позволяет новому образцу начаться на текущем символе независимо от прежних совпадений. Без неё нулевое начальное состояние оставалось бы нулевым навсегда.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Juha Kärkkäinen: Exact String Matching, Algorithm2.8
Прочитаны битовый инвариант всех совпавших префиксов, update Shift-And и условие m≤w для постоянной стоимости. Собственный образец aab и два перекрывающихся начала в aaabaab проверены всеми окнами; код KMP источника не используется.
Алгоритм Дюваля и единственная факторизация на слова Линдона
Каждая непустая строка единственным образом разбивается на лексикографически невозрастающие слова Линдона. Алгоритм Дюваля находит это разбиение тремя движущимися индексами. Он выделяет канонические блоки по порядку символов, а не по совпадению с фиксированным префиксом всей строки.
Перед началом: Лексикографический порядок строк; Циклический сдвиг непустого слова.
Факторы должны удовлетворять двум разным условиям
Непустое слово называется словом Линдона, если оно строго меньше каждого своего нетривиального циклического сдвига. Односимвольное слово удовлетворяет условию автоматически. Строгость исключает нетривиальные степени: у повторённого блока найдётся равный циклический сдвиг.
В факторизации w=u₁u₂…u_r каждый блок должен быть словом Линдона, а сами блоки располагаются как u₁≥u₂≥…≥u_r. Одного из этих условий недостаточно. Разбиение на отдельные буквы даёт слова Линдона, но может нарушить невозрастание; подходящий порядок произвольных блоков не гарантирует их внутреннюю минимальность. Теорема Чена — Фокса — Линдона утверждает существование и единственность такой совместной записи.
Три индекса сравнивают продолжение с текущим кандидатом
Пусть i — начало ещё не разобранного суффикса. Установим j=i+1,k=i. Пока j не вышел за строку и w[k]≤w[j], продолжаем сравнение: при строгом меньшем символе сбрасываем k к i, при равенстве увеличиваем k; затем увеличиваем j. Так хранится участок, являющийся повторением кандидата с возможным неполным последним повтором.
Остановка на меньшем символе или на конце фиксирует длину d=j−k. Блок длины d выводится с текущего i, после чего i увеличивается на d; это повторяется, пока i≤k. Затем начинается новый внешний этап. Строгие и нестрогие сравнения имеют разные роли: замена одного знака способна склеить повторённый блок в слово, которое уже не является словом Линдона.
Линейность относится к сравнениям, а не к явному перебору сдвигов
Хотя определение слова Линдона использует все циклические сдвиги, алгоритм их не строит. На каждом этапе j движется вправо, а завершённые блоки больше не разбираются. Стандартный учёт пройденных участков даёт линейное число сравнений и постоянную дополнительную память, если не считать список результата.
Для короткого примера полезно независимо проверить факторы прямым перечислением вращений. Это медленная проверка определения, которая не используется как основной алгоритм. Затем отдельно проверяют порядок соседних факторов и их конкатенацию. Эти три проверки выявляют разные ошибки: неверный внутренний блок, неверный порядок и потерянные символы.
Четыре канонических блока
Условие. Найдите факторизацию Дюваля строки cababbaba при обычном порядке a<b<c. Проверьте результат по определению и объясните, почему нельзя заменить ababb двумя блоками ab и abb.
- Первый символ c больше следующего a, поэтому первый завершённый фактор равен c. Неразобранный суффикс теперь ababbaba.
- Сравнения на следующем этапе доходят до конца строки с периодом кандидата пять. Выводится фактор ababb; остаётся aba.
- Для оставшегося суффикса получается фактор ab, затем последний односимвольный фактор a. Полная запись: c|ababb|ab|a.
- Все нетривиальные вращения ababb — babba, abbab, bbaba, babab — больше исходного слова. Для ab единственное вращение ba также больше; односимвольные блоки допустимы.
- Порядок факторов невозрастает: c>ababb>ab>a. Если разбить ababb как ab|abb, получится возрастание ab<abb, поэтому такая запись не является требуемой факторизацией.
Ответ. Факторизация равна c|ababb|ab|a. Она содержит четыре слова Линдона в строго убывающем здесь лексикографическом порядке.
Проверка. Конкатенация возвращает девять исходных символов. Перебор вращений проверяет каждый фактор, а независимый перебор всех разбиений короткой строки оставляет только одну допустимую последовательность.
Где легко ошибиться. Не путайте равенство нескольких повторённых блоков с одним словом Линдона. Строгая минимальность относительно вращений запрещает нетривиальную степень внутри фактора.
Проверьте понимание
Вопросы к этой главе
Могут ли соседние факторы быть равны?
Да. Требуется невозрастание, а не строгое убывание. Например, повтор одного и того же слова Линдона даёт несколько равных факторов, а не обязательно один более длинный фактор.
Зависит ли факторизация от порядка алфавита?
Да. Сравнение букв определяет и минимальность вращений, и порядок факторов. При другом порядке результат нужно вычислять заново, даже если сама последовательность символов сохранилась.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Ghuman, Giaquinta, Tarhio: Alternative algorithms for Lyndon factorization
Прочитаны определения в §2 и описание классического алгоритма Дюваля в §3 с LF-Duval. Специальные улучшения для сжатых строк не используются. Девятисимвольная строка, её вращения и проверка уникальности рассчитаны независимо.
Палиндромное дерево хранит разные палиндромы, а не все центры
Один палиндром может встречаться в тексте много раз и иметь разные центры. Eertree хранит его одним узлом, а добавление символа создаёт не более одного нового узла. Суффиксные ссылки позволяют искать подходящее симметричное расширение среди уже известных палиндромных окончаний, не перебирая все подстроки нового префикса.
Перед началом: Палиндром и собственный суффикс строки; Ссылки на более короткие допустимые окончания.
Два корня обслуживают нечётную и чётную длину
Посимвольное добавление справа в конечную строку; считаются разные непустые палиндромные подстроки, а не их вхождения.
У каждого обычного узла v есть длина палиндрома и переход по символу c к палиндрому cvc, если такой встречается. Корень длины 0 представляет пустую середину и создаёт двухбуквенные палиндромы cc. Служебный корень длины −1 задаёт особый переход к односимвольному c. Отрицательная длина является устройством алгоритма, а не настоящей подстрокой.
Суффиксная ссылка обычного узла указывает на самый длинный собственный палиндромный суффикс его слова. У односимвольных узлов она ведёт в длину 0; корень 0 ссылается на −1, а −1 — на себя. Переход расширения и суффиксная ссылка имеют разные смыслы и не должны храниться как одна неразличимая связь.
Новый палиндром может быть только самым длинным окончанием
После добавления символа все впервые появившиеся подстроки заканчиваются на нём. Если новый палиндром v короче другого палиндромного суффикса w, то v одновременно является префиксом w: обращение переносит палиндромный суффикс в равный префикс. Этот префикс оканчивается раньше последнего символа и уже был в тексте. Значит новым может оказаться только самый длинный палиндромный суффикс.
Храним узел last этого суффикса предыдущего префикса. Для нового символа позиции i проверяем симметричную букву i−1−len(v). Если индекс допустим и буква совпала, v расширяется; иначе идём по суффиксной ссылке. Корень −1 гарантирует остановку, поскольку сравнение тогда приходится на сам новый символ. Проверка отрицательного индекса обязательна: отрицательный индекс языка программирования не означает допустимую позицию слева.
Повторное расширение переиспользует существующий узел
Если переход найденного v по c уже существует, last получает его цель и число разных палиндромов не растёт. Иначе создаём узел длины len(v)+2. Для длины 1 ссылка известна сразу; для большей длины ищем расширяемый суффикс, начиная со ссылки v, и берём его переход по c. Так одновременно определяется самый длинный собственный палиндромный суффикс нового узла.
Всего обычных узлов не больше длины текста, плюс два служебных. Это не число всех палиндромных вхождений: в строке из одинаковых букв вхождений квадратично много. Базовый алгоритм с упорядоченными словарями переходов имеет суммарную оценку O(n log σ); один вызов добавления всё же может пройти длинную цепочку ссылок. Отдельное постоянное время каждого вызова из линейного размера структуры не следует.
Два повторных символа не создали новых слов
Условие. Постройте множество узлов eertree для строки abcabaab. Укажите новый палиндром и самый длинный палиндромный суффикс после каждого добавления; служебные корни не считайте палиндромами.
- Первые символы a,b,c создают три односимвольных узла. После префиксов abca и abcab самые длинные палиндромные окончания равны a и b; оба уже известны, поэтому новых узлов нет.
- Добавление следующего a даёт префикс abcaba и новый суффикс aba. Его переход идёт от узла b по a, а суффиксная ссылка ведёт в a.
- Следующий a создаёт aa расширением корня длины 0. У нового узла ссылка также ведёт в a. Последний b создаёт baab расширением aa по b; его самый длинный собственный палиндромный суффикс b.
- В итоге разные палиндромы: a,b,c,aba,aa,baab — шесть обычных узлов. Последовательность длин last равна 1,1,1,1,1,3,2,4; число созданий на шагах равно 1,1,1,0,0,1,1,1.
Ответ. Строка имеет 6 разных непустых палиндромов и 8 узлов eertree с двумя служебными. Последний узел соответствует baab и ссылается на b.
Проверка. Независимый перебор всех срезов с проверкой обращения находит то же множество. Всего палиндромных вхождений 11: четыре a, три b и по одному c,aba,aa,baab; это отличается от шести разных значений.
Где легко ошибиться. Не увеличивайте счёт разных палиндромов при каждом найденном палиндромном суффиксе. Существующий переход означает повтор уже сохранённого слова.
Проверьте понимание
Вопросы к этой главе
Почему aa строится из пустого корня, а a — из корня −1?
Добавление одинаковой буквы с двух сторон пустой середины даёт длину 2. Для односимвольного случая формальная длина −1 после прибавления 2 даёт 1; специальный корень объединяет этот случай с общим правилом.
Можно узнать число вхождений по одному числу узлов?
Нет. Узлы представляют различные слова. Для частот нужны дополнительные счётчики и распространение по суффиксным ссылкам либо отдельный подсчёт; в worked вхождения проверены независимым перебором.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Rubinchik & Shur — EERTREE, §2.2
Два служебных корня, суффиксные ссылки и не более одного нового палиндрома при добавлении. Строка abcabaab, последовательность созданий и независимые частоты вычислены отдельно.
Два периода вынуждают общий период только после порога Файна—Уилфа
Период конечного слова не требует делимости его длины. Из наличия периодов p и q поэтому нельзя без условия заключать наличие периода gcd(p,q). Теорема Файна—Уилфа даёт достаточную длину p+q−gcd(p,q). Равенства между позициями удобно представить графом: каждая компонента должна получить одну букву. На коротком слове отдельные компоненты ещё могут не соединиться.
Перед началом: Период конечного слова и граница строки; Наибольший общий делитель целых чисел.
Период задаёт равенства только внутри доступного перекрытия
Конечные слова, положительные целые периоды, равенство символов на перекрытии.
Число p является периодом слова длины n, если s[i]=s[i+p] для всех 0≤i<n−p. Утверждение не сравнивает буквы за концом строки. Для двух периодов построим неориентированный граф позиций 0,…,n−1: соединим пары на расстояниях p и q. Равенства распространяются по путям, поэтому буква постоянна на каждой компоненте.
Все рёбра сохраняют остаток по d=gcd(p,q). Однако обратное не следует автоматически: одинаковый остаток ещё не означает существование пути в конечном диапазоне. Ограничение длины может оборвать необходимые промежуточные позиции. Именно эту потерю связности не учитывает ошибочное рассуждение о периодичности бесконечного продолжения.
Достаточный порог соединяет необходимые классы
Теорема Файна—Уилфа утверждает: если n≥p+q−d и слово имеет периоды p и q, то d также является его периодом. В графовой формулировке при такой длине позиции одного остатка по d оказываются связаны. Для применения проверяют именно длину доступного слова, а не длину предполагаемого продолжения.
Теорема даёт достаточное условие для любых букв. Отдельное короткое слово вполне может иметь период d и без достижения порога: постоянная строка служит простым примером. Поэтому недостаточная длина означает отсутствие общего сертификата, а не обязательное нарушение меньшего периода. Также не требуется называть порог наименьшим для каждой вырожденной пары p,q.
Разные компоненты дают конструктивный контрпример
Чтобы проверить необходимость ограничения в конкретной паре, строим граф на меньшей длине и присваиваем разным компонентам разные символы. Все исходные рёберные равенства выполнятся автоматически. Затем проверяем, разделены ли позиции, которые должен был бы уравнять период d. Это даёт содержательный контрпример без перебора догадок о буквах.
Такой анализ полезен при объединении сведений о повторяющихся фрагментах. Два локальных сдвига ещё не устанавливают минимальный период всего окна. Граф показывает, какие равенства уже доказаны и какого перекрытия не хватает; он отделяет действительное ограничение данных от привычного образа бесконечно повторяющегося блока.
Периоды 5 и 7 на границе достаточной длины
Условие. Для p=5 и q=7 найдите достаточную длину, вынуждающую период 1. Постройте слово длины на единицу меньше, имеющее оба периода, но не период 1.
- Общий делитель равен 1, поэтому теорема даёт порог 5+7−1=11. На длине 10 граф равенств имеет компоненты {0,2,4,5,7,9} и {1,3,6,8}.
- Присвоим первой компоненте a, второй b. Получим ababaababa. Все пары позиций на расстоянии 5 или 7 принадлежат одной компоненте, следовательно оба периода выполняются.
- Соседние позиции 0 и 1 имеют разные буквы. Поэтому период 1 отсутствует, хотя длина 10 почти достигла порога. Нельзя заменить достаточное число 11 на 10 для всех слов этой пары периодов.
- При добавлении позиции 10 равенство с позицией 5 требует букву a, а равенство с позицией 3 — b. Контрпример нельзя продлить с сохранением обоих периодов; граф на длине 11 соединяет обе прежние компоненты.
Ответ. Достаточная длина равна 11. Слово ababaababa длины 10 имеет периоды 5 и 7, но не 1.
Проверка. Независимая проверка всех допустимых пар индексов подтверждает оба периода контрпримера. Перебор всех двоичных слов длины 11 оставляет при этих двух периодах только две постоянные строки; отдельный поиск компонент графа также даёт одну компоненту.
Где легко ошибиться. Не продолжайте конечное слово периодически сразу двумя способами без проверки согласованности новых позиций. Именно на следующей позиции два допустимых локальных продолжения могут потребовать разные буквы.
Проверьте понимание
Вопросы к этой главе
Обязана ли длина слова делиться на каждый его период?
Нет. Определение сравнивает только существующее перекрытие. Делимость требуется для представления слова целым числом одинаковых блоков, а это более сильное свойство.
Если длина меньше порога, можно ли отвергнуть период gcd(p,q)?
Нет. Можно лишь отказаться от вывода по одной теореме. У конкретного слова меньший период проверяют непосредственно; постоянная строка имеет период 1 при любой положительной длине.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Rankin — Fine-Wilf graphs, §1
Классический достаточный порог для двух периодов и граф равенств позиций. Компоненты и двоичный контрпример для периодов 5 и 7 вычислены независимо.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Z-функция строки: длины совпадения с её началом
Z-функция без путаницы с префикс-функцией: совпадение от текущей позиции, правая граница известного блока и длина результата.
Открыть темуРасстояние редактирования: вставить, удалить или заменить символ
Как получается расстояние Левенштейна: префиксы строк, вставка, удаление, замена и проверка минимального пути.
Открыть тему