Алгоритмы строк: подпоследовательность, правки и границы совпадений
Выберите задачу сравнения строк: общая подпоследовательность, расстояние правок, префикс- или Z-функция. Разведите стоимость преобразования и точное совпадение фрагментов.
Задачи модуля
Сначала уточним, разрешены ли пропуски, требуется ли непрерывный фрагмент или нужно преобразовать одну строку в другую. Эти ограничения меняют задачу и смысл ответа сильнее, чем выбор похожего названия алгоритма.
Затем сравним префикс-функцию с Z-функцией по направлению совпадения и соглашению о нулевой позиции. Инструмент показывает путь единичных вставок, удалений и замен; массивы точного сопоставления из других статей проверяются по их определениям отдельно.
Различать подстроку, подпоследовательность и преобразование строки правками.
Проверять единичную стоимость пути редактирования на коротких строках.
Вычислять значения префикс- и Z-функций, соблюдая направление и нумерацию.
Алгоритмы строк
Префикс-функция: откат к границе без повторного чтения
После несовпадения в строковом поиске не нужно возвращать указатель текста назад. Уже совпавший фрагмент хранит цепочку собственных границ, по которой можно выбрать следующий допустимый префикс.
Перед началом: Префикс и суффикс строки; Индексация с нуля.
Состояние означает длину, а не позицию текста
Префикс-функция π[i] равна длине наибольшего собственного префикса строки s[0..i], который одновременно является её суффиксом. Собственный означает короче всей рассматриваемой строки. Перед обработкой s[i] кандидат j=π[i−1] описывает уже известную границу предыдущего префикса. Если s[i]=s[j], границу можно продолжить на один символ. При несовпадении проверяется не любой меньший j, а следующая граница уже совпавшей части.
Почему откат равен π[j−1]
Любой более короткий пригодный кандидат должен быть границей префикса длины j. Самая длинная такая граница имеет длину π[j−1]. Поэтому переход сохраняет все возможные решения и не пропускает подходящий префикс. Откат повторяется, пока символы не совпадут или j не станет нулём. Текущий символ текста остаётся тем же: мы меняем только гипотезу о длине совпавшего префикса, а не перечитываем весь найденный участок.
Линейность следует из суммарного движения
Успешное продолжение увеличивает j не больше чем на единицу на каждой позиции. Каждый откат уменьшает его, и общий запас таких уменьшений ограничен накопленными увеличениями. Поэтому вложенный цикл даёт линейное суммарное число сравнений. В поиске шаблона после полного совпадения переходят к его собственной границе, чтобы не потерять перекрывающиеся вхождения. Если вместо этого обнулить состояние, некоторые ответы исчезнут. Для пустого шаблона нужна отдельная договорённость, поскольку обычное обращение к символу шаблона уже недопустимо.
Если шаблон содержит один символ, его собственная граница имеет длину нуль. Это простой граничный тест индексации: обращение к π[j−1] при j=0 недопустимо. Сначала проверяют ненулевой кандидат, затем выполняют откат.
Несовпадение внутри повторения
Условие. Найдите π для строки abacababac и объясните обработку позиции 7.
Для префикса abacaba значения равны 0,0,1,0,1,2,3.
На позиции 7 стоит b, кандидат j=3 указывает на c, поэтому совпадения нет.
Откатываемся к π[2]=1; символ шаблона с индексом 1 равен b, значит новое значение 2.
Следующие a и c продолжают границу до 3 и 4.
Ответ. π=[0,0,1,0,1,2,3,2,3,4].
Проверка. Последняя граница abac действительно совпадает с концом строки; перебор всех собственных префиксов каждой позиции подтверждает массив.
Где легко ошибиться. При откате используйте π[j−1], а не j−1: последовательное уменьшение теряет линейную оценку и смысл цепочки границ.
Проверьте понимание
Вопросы к этой главе
Почему весь префикс не считается границей?
Иначе π[i] всегда была бы i+1 и не давала бы информации для следующего сравнения.
Нужно ли сдвигать текст при откате?
Нет. Текущий символ ещё не обработан окончательно; меняется только предполагаемая длина совпадения.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Начальные слайды Prefix Function: собственная граница и переход p[j−1]. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Z-функция: что разрешает уже известное окно
Известное совпадающее окно позволяет копировать часть ответов, но только до своей правой границы. За этой границей каждый новый символ нужно сравнить с префиксом заново.
Перед началом: Префикс строки; Полуинтервалы.
Определите окно без смешения границ
Z[i] — длина общего префикса всей строки и суффикса, начинающегося в i. Будем хранить наиболее правое известное окно [l,r), совпадающее с префиксом длины r−l. Для позиции i внутри окна соответствующая позиция префикса равна i−l. Уже вычисленное Z[i−l] можно использовать, но гарантированная длина ограничена r−i. Поэтому начальное значение равно минимуму этих двух чисел. Здесь r не входит в окно, что устраняет неоднозначность последнего символа.
Граница копирования не обещает несовпадения
Если скопированное значение меньше r−i, известное несовпадение находится внутри окна и ответ завершён. Если оно достигает границы, за r ничего ещё не известно. Тогда сравнения продолжают явно. Получив более правое совпадение, обновляют окно. Копирование полного старого Z без минимума может перескочить через неизвестные символы и завысить ответ. Именно этот пограничный случай отличает корректный линейный алгоритм от внешне похожего механического переноса чисел.
Линейная оценка учитывает правую границу
Сравнения за пределами окна либо увеличивают r, либо один раз завершаются несовпадением для текущей позиции. Правая граница двигается только вперёд и не превосходит длину строки. Поэтому суммарная работа линейна. Значение Z[0] выбирают по соглашению — нуль или длина строки; оно не должно менять остальные ответы. Для поиска шаблона через разделитель нужен символ вне обоих алфавитов либо явная обработка границы, иначе совпадение может неправильно перейти из шаблона в текст.
При i≥r никакого копируемого знания нет и длину начинают с нуля. Окно нулевой длины тоже допустимо, но не должно создавать фиктивное совпадение на пустом участке.
Копирование у правого края
Условие. Найдите Z строки abacababac, положив Z[0]=0.
Позиция 2 даёт совпадение a длины 1; позиция 4 даёт aba длины 3, окно [4,7).
На позиции 5 копируется нулевое значение Z[1].
На позиции 6 гарантирована только одна буква: min(Z[2],7−6)=1. Явное продолжение даёт abac длины 4 и новое окно [6,10).
Остальные позиции дают 0,1,0; полный массив готов.
Ответ. Z=[0,0,1,0,3,0,4,0,1,0].
Проверка. Прямое посимвольное сравнение каждого суффикса с началом подтверждает все значения, особенно расширение с 1 до 4 на позиции 6.
Где легко ошибиться. Скопированное значение на границе окна является нижней гарантией, а не окончательным ответом.
Проверьте понимание
Вопросы к этой главе
Почему окно хранится наиболее правым?
Тогда повторные явные сравнения амортизируются продвижением одной общей границы.
Чем Z отличается от π?
Z смотрит от позиции вперёд на совпадение с началом всей строки, а π описывает границу префикса, заканчивающегося в позиции.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Раздел Z Function: совпадение с префиксом и граница известного окна. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Редакционное расстояние: перестановка букв не одна стандартная правка
Расстояние между строками зависит от разрешённых операций. Если модель допускает только вставку, удаление и замену символа, обмен соседних букв нельзя незаметно считать одним шагом.
Перед началом: Динамическое программирование; Префиксы строк.
Состояние фиксирует два префикса
Пусть D[i,j] — минимальная стоимость преобразования первых i символов исходной строки в первые j символов целевой. Границы D[i,0]=i и D[0,j]=j соответствуют удалениям и вставкам. Последний шаг либо удаляет символ, либо вставляет, либо сопоставляет два последних символа с ценой нуль при равенстве и один при замене. Минимум этих трёх вариантов охватывает все допустимые окончания скрипта. Таблица относится именно к выбранной единичной стоимости.
Транспозиция меняет рекурсию
Если добавить обмен соседних символов, появится дополнительный переход через две позиции, причём разновидности такого расстояния различаются правилами повторного использования символов. Поэтому название «редакционное расстояние» без перечня операций неоднозначно. Нельзя вычислить стандартную таблицу Левенштейна, а затем объявить обмен одной операцией в объяснении. В прикладной задаче стоимость опечаток, пробелов и нормализация регистра должны быть зафиксированы до вычисления, иначе ответ сравнивает другую модель.
Скрипт и нижняя граница проверяют оптимальность
Обратный проход по таблице даёт один оптимальный скрипт; при равных минимумах их может быть несколько. Чтобы независимо подтвердить ответ в маленьком примере, предъявляют допустимый скрипт и исключают все более короткие. Различие длины строк даёт простую нижнюю границу, но при равных длинах она нулевая и часто бесполезна. Тогда проверяют, может ли одна допустимая операция изменить строку нужным образом. Этот аргумент не повторяет динамическую программу и помогает обнаружить ошибку модели.
При различных стоимостях операций сравнение двух замен и удаления со вставкой нужно повторить: оптимальный скрипт может измениться даже для той же пары строк.
Поменявшиеся соседи
Условие. Найдите расстояние Левенштейна между form и from при единичных вставке, удалении и замене.
Строки имеют одинаковую длину и различаются в двух средних позициях.
Две замены o→r и r→o дают скрипт стоимости 2.
Одна вставка или удаление меняет длину, поэтому не может дать целевую строку.
Одна замена меняет лишь одну позицию, а различаются две; стоимость 1 невозможна.
Ответ. Расстояние равно 2; при отдельной разрешённой транспозиции оно могло бы стать 1.
Проверка. Полная таблица префиксов даёт D[4,4]=2; независимая нижняя граница исключает все одношаговые скрипты.
Где легко ошибиться. Не добавляйте операцию обмена только в словесный разбор: она должна присутствовать в математической модели и рекурсии.
Проверьте понимание
Вопросы к этой главе
Может ли быть несколько оптимальных скриптов?
Да. Минимальная стоимость может достигаться разными наборами вставок, удалений и замен.
Сначала нужно привести строки к одному регистру?
Только если такая нормализация предусмотрена задачей. Иначе она незаметно меняет входные данные.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Раздел Edit Distance: вставка, удаление, замена; свой двухсимвольный обмен исследован в этой модели. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Полиномиальный хеш: равенство требует проверки текста
Скользящий хеш быстро отсеивает большинство окон, но совпавшее число не доказывает совпадение строк. Маленький модуль позволяет построить коллизию вручную и увидеть границу гарантии.
Перед началом: Остатки по модулю; Геометрическая прогрессия.
Число кодирует строку с потерями
Для кодов символов a_i определим h=∑a_i b^(m−1−i) mod p. Одинаковые строки дают одинаковый хеш, но обратное неверно: возможных строк больше, чем p значений. Даже простота модуля не делает отображение взаимно однозначным. Она полезна для вероятностного анализа некоторых семейств хешей, но не устраняет сам принцип Дирихле. Равенство длин необходимо проверять отдельно, если хеш используется для сравнения произвольных фрагментов.
Сдвиг окна имеет точную формулу
Для окна длины m вычитают код уходящего символа, умноженный на b^(m−1), затем умножают остаток на b и добавляют входящий символ. Всё считают по модулю p. В языке с отрицательным остатком результат нужно нормировать в согласованный диапазон. Предварительная степень должна соответствовать именно длине окна; ошибка на единицу меняет все последующие хеши, хотя первый мог быть вычислен правильно.
Проверка символов меняет гарантию и стоимость
В алгоритме Рабина — Карпа совпадение хеша запускает точное сравнение. Тогда ложного положительного ответа не будет, но многочисленные коллизии могут ухудшить время. Если точное сравнение пропущено, алгоритм становится вероятностным при случайном выборе параметров и требует оценки риска. Два модуля уменьшают риск при подходящих предположениях, но не превращают конечный отпечаток в доказательство равенства. Для недоверенного входа нельзя считать случайность данных универсальным аргументом производительности.
Для проверки реализации полезно сравнить каждый обновлённый хеш с независимым вычислением с нуля на том же окне. Такой тест обнаруживает ошибку степени и нормировки остатка, но не доказывает отсутствие коллизий; эти два свойства нельзя смешивать.
Коллизия и следующее окно
Условие. Коды a=1,b=2,c=3, основание 3, модуль 5. Сравните ab и ca и обновите хеш окна ab в тексте abc.
h(ab)=1·3+2=5≡0.
h(ca)=3·3+1=10≡0, хотя строки различаются.
Для сдвига ab→bc вычитаем 1·3, умножаем на 3 и добавляем 3: (0−3)·3+3=−6≡4.
Прямой расчёт h(bc)=2·3+3=9≡4 подтверждает обновление.
Ответ. ab и ca имеют коллизию 0; следующее окно bc имеет хеш 4.
Проверка. Посимвольное сравнение отвергает ab=ca, а две независимые формулы дают одинаковый хеш bc.
Где легко ошибиться. Простой модуль не исключает коллизии. Гарантия точного совпадения появляется только после проверки исходного содержимого.
Проверьте понимание
Вопросы к этой главе
Почему не хранить само большое число без модуля?
Его размер растёт с длиной строки, и арифметика перестаёт быть постоянной по стоимости; модуль удерживает короткое состояние.
Два хеша дают абсолютную гарантию?
Нет. Они дают больше возможных отпечатков, но при конечном диапазоне коллизии всё равно возможны.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Полиномиальный скользящий отпечаток и необходимость точного сравнения после совпадения хеша. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Суффиксный массив: посчитать разные подстроки через LCP
Каждый суффикс приносит свои префиксы, то есть подстроки исходного текста. После лексикографической сортировки достаточно вычесть совпадение с предыдущим суффиксом, чтобы убрать уже встречавшиеся варианты.
Перед началом: Лексикографический порядок; Подстрока.
Все подстроки появляются как префиксы суффиксов
У строки длины n суффикс, начинающийся в i, имеет n−i непустых префиксов. Без учёта повторов суммарное число равно n(n+1)/2. Суффиксный массив хранит стартовые позиции в порядке самих суффиксов. LCP соседей — длина их наибольшего общего префикса. Пустую подстроку считаем отдельно, если она нужна; стандартная формула в этой главе относится только к непустым.
Почему достаточно одного соседа
Все строки, имеющие данный префикс, стоят подряд в лексикографическом порядке. Поэтому максимальная длина префикса текущего суффикса, уже встречавшегося среди предыдущих, достигается у непосредственного предшественника. Ровно LCP его коротких префиксов уже известны, остальные новые. Следовательно, число различных непустых подстрок равно сумме длин суффиксов минус сумма соседних LCP. Это рассуждение доказывает отсутствие двойного вычитания и не требует перечислять все пары суффиксов.
Терминатор и алфавит входят в договорённость
Некоторые построения добавляют специальный минимальный символ в конец. Он помогает сортировке, но подстроки, содержащие его, не принадлежат исходному тексту и не должны попасть в итоговый счёт. Аналогично, порядок символов должен быть согласован: сравнение Unicode-кодов и языковая сортировка могут быть разными задачами. Единица строки тоже должна быть определена: кодовая точка и видимый составной символ не всегда совпадают. Для короткой строки полезно независимо построить множество всех срезов. Такой перебор квадратичен по количеству кандидатов, но служит отличной конечной проверкой формулы.
Если повторов нет, сумма LCP равна нулю и формула возвращает все n(n+1)/2 вхождения как разные строки. На полностью одинаковых символах LCP образуют возрастающую цепочку и оставляют ровно n разных длин. Эти противоположные крайние случаи хорошо проверяют смысл вычитания.
Небольшой текст с повторением
Условие. Посчитайте различные непустые подстроки строки cacao.
Суффиксы в порядке: acao, ao, cacao, cao, o; стартовые позиции 1,3,0,2,4.
Соседние LCP равны 1,0,2,0.
Сумма длин всех суффиксов равна 5·6/2=15.
Вычитаем 3 повторных префикса и получаем 12.
Ответ. У cacao ровно 12 различных непустых подстрок.
Проверка. По длинам их числа равны 3,3,3,2,1; сумма также 12. Никакой добавленный терминатор в ответ не включён.
Где легко ошибиться. LCP нужно считать между соседями в отсортированном массиве, а не между суффиксами в исходном порядке.
Проверьте понимание
Вопросы к этой главе
Почему повторный короткий префикс не вычитается много раз?
Каждый новый суффикс добавляет только ранее неизвестные префиксы; повторные исключаются один раз из его собственного вклада.
Можно ли так считать вхождения?
Формула считает разные строки-подстроки. Количество всех вхождений с повторами равно исходной сумме длин.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
Определения отсортированных суффиксов и соседних LCP; формула числа подстрок обоснована в главе. Проверены релевантные определения и условия, а не прочитан весь учебник. Условия задач и расчёты главы подготовлены отдельно.
Связанные методы
Чем общая подпоследовательность отличается от общего подотрезка строки
Общая подпоследовательность получается удалением символов из обеих строк без перестановки оставшихся. Её символы не обязаны стоять рядом. Общая подстрока, напротив, должна быть непрерывным фрагментом каждой строки.
Расстояние редактирования: вставить, удалить или заменить символ
Расстояние Левенштейна — минимальное число вставок, удалений и замен символов, превращающих одну строку в другую, когда каждая правка стоит единицу. Совпадение ничего не стоит. Это сравнение записи строк, а не оценка правильности слова или близости значений.
Префикс-функция: как искать границу совпавшего фрагмента
Префикс-функция π[i] хранит длину наибольшего собственного префикса строки s[0…i], который одновременно является её суффиксом. Слово «собственный» исключает всю обработанную строку целиком. Позиции здесь начинаются с нуля, поэтому π[0]=0.