Таблица хорошего суффикса
Вы пишете свой поиск по образцу на манер grep — алгоритмом Бойера — Мура. Таблицу плохой буквы построить просто. Сложнее вторая, таблица хорошего суффикса: она нужна, когда конец образца уже совпал с текстом, а следующая буква — нет. Образцы бывают длинными, до ста тысяч знаков, и таблицу надо строить быстро.
Образец p длины m, позиции с нуля. Пусть окно сравнивалось справа налево, буквы p[i + 1..m − 1] совпали с текстом, а p[i] — нет. Что известно о тексте под окном: справа — те же буквы, что p[i + 1..m − 1], а под позицией i — буква, не равная p[i]. Сдвиг s (1 ≤ s ≤ m) не противоречит этому, если
- p[k − s] = p[k] для всех k от i + 1 до m − 1, у которых k − s ≥ 0;
- и, если i − s ≥ 0, то p[i − s] ≠ p[i].
Позиции, которые после сдвига уходят левее начала образца, ничем не ограничены. Значение gs[i] — наименьший такой сдвиг. Сдвиг m подходит всегда. Для каждого образца выведите всю таблицу gs[0], …, gs[m − 1].
Для образца AT-THAT из статьи Бойера и Мура 1977 года таблица — 5 5 5 5 5 3 1: если совпало «T», а «A» перед ним нет, окно сдвигается на 3 — так, что под совпавшим «T» встаёт «T» из середины образца, перед которым стоит «-», а не «A». Среди тестов — фразы «Войны и мира», теломера, куски генома фага лямбда, слова Фибоначчи и Туэ — Морса.
Вход
В первой строке — число образцов q (1 ≤ q ≤ 1000). В каждой из следующих q строк — образец: непустая строка UTF-8 без переводов строки, пробелы — обычные знаки. Суммарная длина образцов не больше 100 000 знаков; длины и позиции считаются в знаках, а не в байтах.
Выход
Для каждого образца — строка из m чисел через пробел: gs[0], …, gs[m − 1].
Примеры
Пример 1
2 AT-THAT EXAMPLE
5 5 5 5 5 3 1 6 6 6 6 6 6 1
Пример 2
3 abracadabra колокол aaaa
7 7 7 7 7 7 7 10 10 3 1 4 4 4 4 7 7 1 1 2 3 4
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Проверить определение в лоб можно для каждой пары (i, s), но это O(m²) пар и ещё сравнения внутри. Нужен способ узнать за O(1), насколько конец образца совпадает с куском, который кончается в позиции t.
2Подсказка 2
Обозначьте suff[t] — длину самого длинного общего конца у p[0..t] и всего p. Это Z-функция перевёрнутого образца, прочитанная задом наперёд: suff[t] = zrev[m − 1 − t].
3Подсказка 3
Сдвиг s подходит для позиции i в двух случаях. Либо копия совпавшего конца целиком лежит в образце и перед ней другая буква: suff[m − 1 − s] равно ровно m − 1 − i. Либо копия вылезает за левый край: тогда p[0..m − 1 − s] — одновременно начало и конец образца, suff[m − 1 − s] = m − s, и s ≥ i + 1.
4Идея
Каждый кандидат s из первого случая обслуживает ровно одну позицию i = m − 1 − suff[m − 1 − s]. Поэтому все такие сдвиги расставляются одним проходом по t = m − 1 − s: идём слева направо, и для каждой позиции остаётся самая правая копия, то есть самый маленький сдвиг. Второй случай — грани образца: сдвиг до самой длинной грани, которая помещается левее позиции, заполняет все i слева от неё.
5Разбор
Три прохода: Z-функция перевёрнутого образца даёт suff; проход по граням от самой длинной заполняет gs сдвигами второго случая; проход по t слева направо перезаписывает их сдвигами первого случая, которые всегда меньше. Это та же процедура, что в листинге статьи; у Гасфилда она так и называется — Бойер — Мур на Z-функции.
Посмотрите на второй пример. Для «aaaa» таблица 1 2 3 4: если совпали последние k букв «a», а перед ними в тексте не «a», окно должно перешагнуть эту букву целиком — любой меньший сдвиг поставит под неё «a». Слабое правило, которое забывает про несовпавшую букву, даёт везде 1 и на тексте из одних «a» превращает Бойера — Мура в наивный поиск.
5+Решение
6Сложность
O(m) на образец: Z-функция и два прохода. Перебор пар (i, s) с проверкой через suff — O(m²): на образце из ста тысяч знаков это десять миллиардов шагов.
7Типичные ошибки
- Слабое правило. Сдвиг проверяют только на совпадение с концом, без условия p[i − s] ≠ p[i]. Сдвиги остаются безопасными, но короче нужных: у «колокол», когда совпало «ол», а «к» перед ним нет, слабое правило даёт 4 и ставит под несовпавшую букву текста снова «к»; верный ответ — 7.
- Забыть грани. Если совпавший конец нигде больше в образце не стоит целиком, сдвиг не всегда m: начало образца может совпасть с хвостом этого конца. У «abracadabra», когда совпало «bra», а «a» перед ним нет, копия «bra» в начале не годится (перед ней тоже «a»), но сдвиг всё равно не 11, а 10: первая буква образца совпадает с последней буквой совпавшего конца.
- Байты вместо знаков. Таблица строится по буквам: в Go — по
[]rune.