Склейка
Из текста вырезают куски — подряд идущие знаки — и склеивают из них фразу. Кусок можно брать из любого места текста, один и тот же кусок — сколько угодно раз. Для каждой фразы найдите наименьшее число кусков, из которых она склеивается, или скажите, что не склеивается никак: в ней есть знак, которого в тексте нет. Знаки сравниваются точно, пробел — тоже знак.
В третьем тесте текст — «Евгений Онегин», а фразы — предложения «Войны и мира»; в четвёртом наоборот: начало «Войны и мира» и строки «Онегина». Тексты приведены к одному виду: строчные буквы, е вместо ё, один вид тире и кавычек, пробел вместо перевода строки.
Вход
В первой строке — текст длиной от 1 до 2 · 10⁵ знаков. Во второй — число фраз q. Дальше q строк — фразы, в каждой хотя бы один знак, всего во фразах не больше 2 · 10⁵ знаков. Текст и фразы в кодировке UTF-8, без пробелов в начале и в конце; длины считаются в знаках, а не в байтах.
Выход
Для каждой фразы в отдельной строке — наименьшее число кусков или -1.
Примеры
Пример 1
колокол 4 око локо кол около клок
1 1 -1 2
Пример 2
abracadabra 4 cadabra barbara abba cab
1 6 3 2
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Пусть фраза начинается с куска длины 5, а кусок длины 7 с того же места тоже есть в тексте. Может ли выгоднее оказаться короткий?
2Подсказка 2
Жадно брать самый длинный кусок — правильно. Осталось быстро узнавать, на сколько знаков можно продлить кусок. Нужна структура, которая на каждую следующую букву за один шаг отвечает: есть ли в тексте такое продолжение.
3Идея
Жадная склейка не длиннее любой другой — это теорема из статьи: жадные разрезы никогда не отстают от разрезов другой склейки, потому что хвост куска, который есть в тексте, тоже есть в тексте. А «есть ли продолжение» отвечает суффиксный автомат текста: из корня можно пройти ровно по подстрокам.
4Разбор
Строим автомат текста по букве. Фразу читаем от начала: идём по переходам, пока они есть, — пройденное и есть самый длинный кусок. Если не удалось сделать ни шага, такого знака в тексте нет, ответ -1. Иначе считаем кусок и начинаем снова от корня с той же позиции фразы. В Python переходы — словари; в Go удобнее списки рёбер в общих массивах: у большинства состояний переходов один-два.
4+Решение
5Сложность
Построение — O(n) для текста длины n, состояний меньше 2n. Каждая фраза — один проход, O(m) для длины m: каждый знак фразы читается один раз.
6Типичные ошибки
- Искать кусок в тексте заново. Это
wrong.py: продлевать кусок по букве и проверятькусок in text. Ответы верные, но каждая проверка просматривает текст, и кусок длины L стоит L · n. В шестом тесте фразы из случайных букв a и b, кусок в среднем 18 знаков, и проверок около двухсот тысяч — каждая по тексту в 2 · 10⁵ знаков; в седьмом кусок в среднем 1770 знаков. - Резать по словам. Кусок может начинаться и кончаться посреди слова: «все с|частливые» — так короче.
- Начинать после неудачи не с корня. Отступ по суффиксной ссылке нужен, чтобы находить общие подстроки, а здесь кусок фразы обязан начинаться ровно там, где кончился предыдущий.
- Байты вместо знаков. Текст в UTF-8: в Go строку надо разобрать на руны, иначе буква кириллицы окажется двумя «знаками», и кусок можно будет разрезать посреди буквы.