- Cтрока — это упорядоченная последовательность символов, символы строки длины n имеют номера с 1 по n (в Паскале) или с 0 по n-1 (в Си), в данной статье будет использоваться нумерация с единицы;
- Префикс строки s — строка t, совпадающая с началом строки s (t = s1s2..sk, где k - длина префикса);
- Суффикс строки s — строка t, совпадающая с концом строки s (t = sn-k+1sn-k+2..sn, где k - длина суффикса);
- Подстрока строки s — строка t, являющаяся префиксом суффикса s (t = slsl+1..sr, где 1 <= l <= r <= n).
Теперь может возникнуть вопрос: зачем по-особенному рассматривать эту группу задач, если в любом уважающем себя языке существуют стандартные операции для работы со строками, и задачи всегда могут решаться "в лоб"? К сожалению, стандартных приёмов не всегда хватает для достижения успеха.
Давайте сразу же рассмотрим в качестве примера серьёзную олимпиадную задачу на строки.
Задача.
Дана некоторая строка s длины N. Приходит M запросов в виде строк ti, на каждый из которых нужно ответить, содержит ли строка s подстроку ti.Известно, что N, M <= 104, а суммарная длина всех строк Et в запросах не превышает 108.
В лобовом решении разобраться нетрудно: можно перебирать каждый символ в строке s, с которого может начинаться ti, а затем поочерёдно проверять символы на совпадение; если какой-то из стартовых символов подошёл, то выводим положительный ответ. Но для каждого из запросов есть O(N) стартовых символов, и для каждого из них проверка осуществляется за O(|ti|) ("модуль" — это длина строки ti). Так как |t1| + |t2| + ... + |tn| = Et, то асимптотика этого решения составит O(N*Et). Стандартные функции по факту работают точно так же, поэтому ситуацию не улучшают. 1012 операций — это нечто совсем неприемлемое, поэтому возникает проблема: задача кажется нерешаемой за адекватное время.
Тем не менее, существует хороший алгоритм, решающий эту и другие задачи на сравнение строк, при этом являющийся одним из самых простых для понимания. Это алгоритм хэширования.
Говоря простым языком, хэширование — это преобразование строки в число. Принцип, по которому происходит преобразование, называется хэш-функцией, а результат в виде числа — хэшом строки. Существует много таких функций, все они обладают различными свойствами; наша же цель — оптимизировать (ускорить) процесс сравнения строк. Для этого мы будем использовать функцию следующего вида (полиномиальный хэш) от строки s длины n:
f(s) = pn-1*s1 + pn-2*s2 + ... + p0*sn
В этой функции используются не сами символы вида si, а их ASCII-коды (от 0 до 255); p — некоторое простое число, строго большее максимального кода, например, 257. Можно заметить, что при таком хэшировании строка преобразуется в число в p-ичной системе счисления, и соблюдается полезное свойство — разным строкам соответствуют разные хэши, а одинаковым — одинаковые. Собственно, для счастья больше ничего и не надо: если надо сравнить две строки, посчитаем их хэши и сравним их. При этом мы получим тот же ответ, но уже за O(1), а не за O(N), так как строки, как уже говорилось, сравниваются посимвольно, а числа — наоборот, очень быстро. Теперь о том, как написать хэш-функцию. Весь значимый код заключается в подсчёте хэша строки, причём попутно мы ещё будем запоминать хэши всех префиксов в массив h. Делается это по такой формуле:
h1 = s1,
hi = hi-1*p + si при i >= 2.
Можно показать, что все хэши будут посчитаны правильно. Конечно, если запоминать хэши префиксов не позволяет ограничение по памяти, то вместо массива можно хранить всего одну переменную h. Формула будет почти та же, только вместо записывания хэша нового префикса мы будем делать переприсвоение переменной:
h = s1,
h = h*p + si при i >= 2.
Кажется, что всё хорошо, но очевидно, что если хранить хэш в типе int64, то число h будет очень быстро расти и даже при небольших строках переполнится. Однако из этой ситуации есть выход: хэши можно брать по некоторому простому модулю (иначе говоря, вместо всего хэша хранить его остаток от деления на простое число). В качестве такого числа хорошо подходит 1000000007 (109+7). Однако есть и другой момент, заключающийся в том, что можно просто не обращать внимание на переполнения, так как при этом хэш будет "как бы" браться по модулю 264. Разумеется, теперь уже нельзя сказать, что разным строкам обязательно соответствуют разные хэши; могут возникать так называемые коллизии (совпадения хэшей у разных строк) и даже существует тест, против которого бессильны хэши с переполнением. И всё же контртесты встречаются далеко не везде и добавляются обычно только при нелюбви автора задачи к хэшам, а вероятность коллизий при хранении хэша в int64 ничтожно мала.
В последнее время авторы задач всё чаще и чаще стали добавлять в свои "творения", которые возможно решать с помощью хэшей, антихэш-тесты, даже если это единственное решение, которое подразумевается авторами, как верное.
Существуют несколько методов борьбы с антихэш-тестами. Вот некоторые из них.
Первый и самый простой способ - хранить не только хэш, но и длину хэшируемого участка, таким образом исключаются коллизии строк с разными длинами.
Второй способ - считать хэши не по одному, а по нескольким простым модулям M или с использованием нескольких простых чисел p. Вероятность совпадения одного хэша не очень велика, а сразу нескольких хэшей для разных строк сильно меньше.
Совет: если задача не получает вердикт "задача зачтена" с M = 264, то есть используя встроенное переполнение переменной, стоит завести отдельную структуру для хэша, в которой удобно будет хранить и хэши по всем модулям, добавлять, менять или удалять сравнения по новым p и M, а также, переопределив оператор ==, сравнивать структуры.
Вернёмся к задаче. Сейчас мы уже умеем считать хэш от целой строки, но этого явно недостаточно: хранить все возможные хэши строки s слишком затратно, а считать их каждый раз заново — слишком долго.
На помощь приходит следующий факт: при хранении хэшей всех префиксов s мы можем за O(1) получить хэш любой подстроки! Допустим, нам нужен хэш подстроки s, содержащей её символы с l до r включительно (slsl+1..sr).
Давайте в самом начале насчитаем все необходимые нам степени числа p (от 0 до N-1) и запишем их в массив pp за O(N) операций, следуя простой формуле:
pp0 = 1,
ppi = ppi-1*p при i >= 1.
Теперь утверждается, что хэш искомой подстроки равен hr - hl-1*ppr-l+1, и при рассмотрении этого выражения получаем, что это действительно так: "ненужные" слагаемые приводятся к большим степеням и сокращаются. После этого ничто не мешает нам снизить асимптотику первоначального решения. Сначала подсчитаем хэши всех префиксов строки s. Далее каждый из M запросов будем обрабатывать таким образом: вначале за O(|ti|) посчитаем хэш ti, а потом за O(N) пройдемся по всем хэшам строки s длины |ti| и проверим каждый из них на совпадение. Получаем O(N + Et) операций на подсчёт всех хэшей и O(M*N) операций на сравнения хэшей. Итоговая асимптотика — O(Et + M*N), 2*108 операций вполне приемлемы.
Примечание: Если размер алфавита меньше 255 (например, если в условии оговаривается, что он состоит только из маленьких латинских букв), то целесообразно брать в качестве числа p число поменьше, например, 31.
Логунов Александр