Здравствуйте! Этот пост написан для всех тех, кто хочет освоить полиномиальные хэши и научиться применять их в решении различных задач. Я кратко приведу теоретический материал, рассмотрю особенности реализации и разберу некоторые задачи, среди них:
Поиск всех вхождений одной строки длины n в другую длины m за O(n + m)
Поиск наибольшей общей подстроки двух строк длин n и m (n ≥ m) за O(n + m·log(m)2)
Нахождение лексикографически минимального циклического сдвига строки длины n за O(n·log(n))
Сортировка всех циклических сдвигов строки длины n в лексикографическом порядке за O(n·log(n)2)
Нахождение количества подпалиндромов строки длины n за O(n·log(n))
Количество подстрок строки длины n, являющихся циклическими сдвигами строки длины m за O((n + m)·log(n))
Количество суффиксов строки длины n, бесконечное расширение которых совпадает с бесконечным расширением всей строки за O(n·log(n)) (расширение — дублирование строки бесконечное число раз).
Примечание 1. Не исключено, что некоторые задачи могут быть решены быстрее другими методами, например, сортировка циклических сдвигов — это в точности то, что происходит при построении суффиксного массива, искать все вхождения одной строки в другую позволит алгоритм Кнута-Морриса-Пратта, с подпалиндромами отлично справляется алгоритм Манакера, а для собственных суффиксов есть префикс-функция.
Примечание 2. В задачах выше приведена оценка, когда поиск хэша осуществляется при помощи сортировки и бинарного поиска. Если у Вас есть своя хэш-таблица с открытым перемешиванием или цепочками переполнения, то Вы — счастливчик, смело заменяйте бинарный поиск хэша на поиск в Вашей хэш-таблице, но не вздумайте использовать std::unordered_set, так как на практике поиск в std::unordered_set проигрывает сортировке и бинарному поиску в связи с тем, что эта штука подчиняется стандарту C++ и обязана много чего гарантировать пользователю, что полезно при промышленной разработке и, зачастую, бесполезно в олимпиадном программировании, поэтому сортировка и бинарный поиск для несложных структур одерживают абсолютное первенство в C++ по скорости работы, если не тянуть что-то свое.
Примечание 3. В тех случаях, когда сравнение элементов затратно (например, сравнение по хэшам за O(log(n))), то в худшем случае std::random_shuffle + std::sort всегда проигрывает std::stable_sort, так как std::stable_sort гарантирует минимальное число сравнений среди всех сортировок (основанных на сравнениях) для худшего случая.
Решение перечисленных задач будет приведено ниже, исходники тоже.
В качестве плюса полиномиального хэширования могу отметить, что зачастую не нужно думать, можно сразу брать и писать наивный алгоритм решения задачи и ускорять его полиномиальным хэшированием. Лично мне решения с полиномиальным хэшем приходят в голову в первую очередь, может поэтому я синий.
Среди минусов полиномиального хэширования: а) Слишком много операций остатка от деления, порой на грани TLE на больших задачах и б) на codeforces в программах на C++ зачастую маленькие гарантии от взлома из-за MinGW: std::random_device генерирует каждый раз одно и то же число, std::chrono::high_resolution_clock тикает в микросекундах вместо наносекунд. (Компилятор cygwin на windows лишен всех недостатков MinGW, в том числе и медленного ввода/вывода).
Что такое полиномиальный хэш?
Хэш-функция должна сопоставлять некоторому объекту некоторое число (его хэш) и обладать следующими свойствами:
Если два объекта совпадают, то их хэши равны.
Если два хэша равны, то объекты совпадают с большой вероятностью.
Коллизией называется очень неприятная ситуация равенства двух хэшей у несовпадающих объектов. В идеале, при выборе хэш-функции необходимо обеспечить как можно меньшую вероятность коллизии. На практике — такую вероятность, чтобы успешно пройти набор тестов к задаче.
Рассмотрим последовательность a[0], a[1], ..., a[n-1]. Под полиномиальным хэшем для этой последовательности будем иметь в виду результат вычисления следующего выражения:
hash(a, p, m) = (a[0] + a[1] * p + a[2] * p^2 + ... + a[n-1] * p^(n-1)) % m
Здесь p и m — точка (или основание) и модуль хэширования соответственно.
Условия, которые мы наложим: max(a[i]) < p < m, gcd(p,m) = 1.
Примечание. Если подумать об интерпретации выражения, то мы сопоставляем последовательности
a[0], a[1], a[2], ..., a[n-1]
число длины n в системе счисления p и берем остаток от его деления на число m, или значение многочлена (n-1)-й степени с коэффициентами a[i] в точке p по модулю m. О выборе p и m поговорим позже.
Примечание. Если значение hash(a, p, m), не взятое по модулю, помещается в целочисленный тип данных (например, 64-битный тип), то можно каждой последовательности сопоставить это число. Тогда сравнение на больше / меньше / равно можно выполнять за O(1).
Сравнение на равенство за O(1)
Теперь ответим на вопрос, как сравнивать произвольные подпоследовательности за O(1)? Покажем, что для сравнения подпоследовательностей исходной последовательности a[0], a[1], ..., a[n-1] достаточно посчитать полиномиальный хэш на каждом префиксе исходной последовательности.
Определим полиномиальный хэш на префиксе как:
pref(k, a, p, m) = (a[0] + a[1] * p + a[2] * p^2 + ... + a[k-1] * p^(k-1)) % m
Кратко обозначим pref(k, a, p, m) как pref(k) и будем иметь в виду, что итоговое значение берется по модулю m. Тогда:
pref(0) = 0, pref(1) = a[0], pref(2) = a[0] + a[1] * p, pref(3) = a[0] + a[1] * p + a[2] * p^2, ...
Общий вид:
pref(n) = a[0] + a[1] * p + a[2] * p^2 + ... + a[n-1] * p^(n-1)
Полиномиальный хэш на каждом префиксе можно находить за O(n), используя рекуррентные соотношения:
p^k = p^(k-1) * p
pref(k+1) = pref(k) + a[k] * p^k
Допустим, нам нужно сравнить две подстроки, начинающиеся в позициях i и j и имеющие длину len, на равенство:
a[i], a[i+1], ..., a[i+len-1] =? a[j], a[j+1], ..., a[j+len-1]
Рассмотрим разности pref(i+len) - pref(i) и pref(j+len) - pref(j). Не трудно видеть, что:
( I) pref(i+len) - pref(i) = a[i] * p^i + a[i+1] * p^(i+1) + ... + a[i+len-1] * p^(i+len-1)
(II) pref(j+len) - pref(j) = a[j] * p^j + a[j+1] * p^(j+1) + ... + a[j+len-1] * p^(j+len-1)
Домножим 1-е уравнение на p^j, а 2-е на p^i. Получим:
( I) p^j * (pref(i+len) - pref(i)) = p^(i+j) * (a[i] + a[i+1] * p^1 + ... + a[i+len-1] * p^(len-1))
(II) p^i * (pref(j+len) - pref(j)) = p^(i+j) * (a[j] + a[j+1] * p^1 + ... + a[j+len-1] * p^(len-1))
Видим, что в правой части выражений в скобках были получены полиномиальные хэши от подпоследовательностей:
a[i], a[i+1], ..., a[i+len-1] и a[j], a[j+1], ..., a[j+len-1].
Таким образом, чтобы определить, совпали ли искомые подпоследовательности, необходимо проверить выполнение следующего равенства:
p^j * (pref(i+len) - pref(i)) = p^i * (pref(j+len) - pref(j))
Одно такое сравнение можно выполнять за O(1), предподсчитав степени p по модулю. С учетом модуля m, имеем:
p^j * (pref(i+len) - pref(i)) % m = p^i * (pref(j+len) - pref(j)) % m
Минусы: сравнение одной строки зависит от параметров другой строки (от j).
Если нам известны максимальные длины сравниваемых строк, то можно применить другой подход. Обозначим максимальную длину сравниваемых строк как mxPow. Домножим (I) на mxPow-i-len+1, а (II) на mxPow-j-len+1. Тогда:
( I) p^(mxPow-i-len+1)*(pref(i+len)-pref(i))=p^(mxPow-len+1)*(a[i]+a[i+1]*p+...+a[i+len-1]*p^(len-1))
(II) p^(mxPow-j-len+1)*(pref(j+len)-pref(j))=p^(mxPow-len+1)*(a[j]+a[j+1]*p+...+a[j+len-1]*p^(len-1))
Можем заметить, что в правых частях был получен полиномиальный хэш от искомых подпоследовательностей. Тогда, равенство проверяется следующим образом:
p^(mxPow-i-len+1) * (pref(i+len) - pref(i)) % m = p^(mxPow-j-len+1) * (pref(j+len) - pref(j)) % m
Этот подход позволяет сравнивать одну подстроку длины len со всеми подстроками длины len на равенство, в том числе, и подстроками другой строки, так как выражение p^(mxPow-i-len+1)*(pref(i+len) - pref(i)) % m для подстроки длины len, начинающейся в позиции i, зависит только от параметров подстроки i, len и константы mxPow, а не от параметров другой подстроки.
Сравнение на больше / меньше за O(log(n))
Рассмотрим две подстроки возможно разных строк длин len1 и len2, (len1 <= len2), начинающиеся в позициях i и j соответственно. Заметим, что отношение больше / меньше определяется первым несовпадающим символом в этих подстроках, а до позиции этого символа строки совпадают. Таким образом, необходимо найти позицию первого несовпадающего символа методом бинарного поиска, а затем сравнить найденные символы. Благодаря сравнению подстрок на равенство за O(1), можно решить задачу сравнения подстрок на больше / меньше за O(log(len1)).
Минимизация вероятности коллизии
Пусть за все время работы программы нам нужно выполнить nCompChars сравнений символов. Грубая оценка:
nCompChars <= nCompStrings * mxLen^2. Тогда вероятность того, что коллизии не произойдет:
p ~=~ 1 - exp(nCompChars / m) ~=~ 1 - exp(nCompStrings * mxLen^2 / m)
Отсюда очевидно, что m нужно брать значительно больше, чем nCompStrings * mxLen^2. Тогда, аппроксимируя экспоненту рядом Тейлора, получаем вероятность коллизии на одном тесте:
p ~=~ 1 - exp(nCompStrings * mxLen^2 / m) ~=~ nCompStrings * mxLen^2 / m
Если мы рассмотрим задачу о поиске вхождений всех циклических сдвигов одной строки в другую строку длин до 10^5, то мы можем получить 10^15 сравнений символов (может показаться, что 10^20, но чем больше длина — тем меньше позиций, в которых реально нужно искать совпадения с текущим циклическим сдвигом, поэтому 10^15).
Тогда, если мы возьмем простой модуль порядка 10^9, то мы не пройдем ни один из максимальных тестов.
Если мы возьмем модуль порядка 10^18, то вероятность коллизии на одном тесте ~=~ 0.001. Если максимальных тестов 100, то вероятность коллизии в одном из тестов ~=~ 0.1, то есть 10%.
Если мы возьмем модуль порядка 10^27, то на 100 максимальных тестах вероятность коллизии равна ~=~ 1e-10.
Вывод: чем больше модуль — тем больше вероятность пройти тест. Эта вероятность не учитывает взломы.
Двойной полиномиальный хэш
Разумеется, в реальных программах мы не можем брать модули порядка 10^27. Как быть? На помощь приходит китайская теорема об остатках. Если мы возьмем два взаимно простых модуля m1 и m2, то кольцо остатков по модулю m = m1 * m2 эквивалентно произведению колец по модулям m1 и m2, т.е. между ними существует взаимно однозначное соответствие, основанное на идемпотентах кольца вычетов по модулю m. Иными словами, если вычислять hash1 по модулю m1 и hash2 по модулю m2, а затем сравнивать две подпоследовательности по hash1 и hash2 одновременно, то это эквивалентно сравнению полиномиальным хэшем по модулю m. Аналогично, можно брать три взаимно простых модуля m1, m2, m3.
Особенности реализации
Итак, мы подошли к реализации описанного выше. Цель — минимум взятий остатка от деления, т.е. получить два умножения в 64-битном типе и одно взятие остатка от деления в 64-битном типе на одно вычисление двойного полиномиального хэша, при этом получить хэш по модулю порядка 10^27 и защитить код от взлома на codeforces.
Выбор модулей. Выгодно использовать двойной полиномиальный хэш по модулям m1 = 1000000123 и m2 = 2^64. Если Вам не нравится такой выбор m1, можете выбрать 1000000321, главное выбрать такое простое число, чтобы разность двух остатков лежала в пределах знакового 32-битного типа (int). Простое число брать удобнее, так как автоматически обеспечиваются условия gcd(m1, m2) = 1 и gcd(m1, p) = 1. Выбор в качестве m2 = 2^64 не случаен. Стандарт C++ гарантирует, что все вычисления в unsigned long long выполняются по модулю 2^64 автоматически. Отдельно модуль 2^64 брать нельзя, так как существует анти-хэш тест, который не зависит от выбора точки хэширования p. Модуль m1 необходимо задать как константу для ускорения взятия модуля (компилятор (не MinGW) оптимизирует, заменяя умножением и побитовым сдвигом).
Кодирование последовательности. Если дана последовательность символов, состоящая, например, из маленьких латинских букв, то можно ничего не кодировать, так как каждому символу уже соответствует его код. Если дана последовательность целых чисел разумной для представления в памяти длины, то можно собрать в один массив все встречающиеся числа, отсортировать, удалить повторы и сопоставить каждому числу в последовательности его порядковый номер в полученном упорядоченном множестве. Начинать нумерацию с нуля запрещено: все последовательности вида 0,0,0,..,0 разной длины будут иметь один и тот же полиномиальный хэш.
Выбор основания. В качестве основания p достаточно взять любое нечетное число, удовлетворяющее условию max(a[i]) < p < m1. (нечетное, потому что тогда gcd(p, 2^64) = 1). Если Вас могут взломать, то необходимо генерировать p случайным образом с каждым новым запуском программы, причем генерация при помощи std::srand(std::time(0)) и std::rand() не подходит, так как std::time(0) тикает очень медленно, а std::rand() не обеспечивает достаточной равномерности. Если компилятор НЕ MinGW (к сожалению, на codeforces установлен MinGW), то можно использовать std::random_device, std::mt19937, std::uniform_int_distribution<int> (в cygwin на windows и gnu gcc на linux данный набор обеспечивает почти абсолютную случайность). Если не повезло и Вас посадили на MinGW, то ничего не остается, как std::random_device заменить на std::chrono::high_resolution_clock и надеяться на лучшее (или есть способ достать какой-нибудь счетчик из процессора?). На MinGW этот таймер тикает в микросекундах, на cygwin и gnu gcc в наносекундах.
Гарантии от взлома. Нечетных чисел до модуля порядка 10^9 тоже порядка 10^9. Взломщику необходимо будет сгенерировать для каждого нечетного числа анти-хэш тест так, чтобы была коллизия в пространстве до 10^27, скомпоновать все тесты в один большой тест и сломать Вас. Это если использовать не MinGW на Windows. На MinGW таймер тикает, как уже говорилось, в микросекундах. Зная время отправки решения, можно для каждой из 10^6 микросекунд вычислить, какое случайное p сгенерировалось, и тогда вариантов в 1000 раз меньше. Если 10^9 это какая-то космическая величина, то 10^6 уже кажется не такой безопасной. При использовании std::time(0) всего 10^3 вариантов (миллисекунды) — можно ломать. В комментариях я видел, что гроссмейстеры умеют ломать полиномиальный хэш до 10^36.
Удобство в использовании. Удобно написать универсальный объект для полиномиального хэша и копировать его в ту задачу, где он может понадобиться. Лучше писать самостоятельно для своих нужд и целей в том стиле, в котором пишете Вы, чтобы разбираться в исходном коде при необходимости. Все задачи в этом посте решены при помощи копирования одного и того же объекта. Не исключено, что существуют специфические задачи, в которых это не сработает.
Задача 1. Поиск всех вхождений одной строки длины n в другую длины m за O(n + m)
Дано: Две строки S и T длин до 50000. Вывести все позиции вхождения строки T в строку S. Индексация с нуля.
Пример: Ввод S = "ababbababa", T = "aba", вывод: 0 5 7.
Задача 2. Поиск наибольшей общей подстроки двух строк длин n и m (n ≥ m) за O(n + m·log(m)2)
Дано: Длина строк N и две строки A и B длины до 100000. Вывести длину наибольшей общей подстроки.
Пример: Ввод: N = 28, A = "VOTEFORTHEGREATALBANIAFORYOU", B = "CHOOSETHEGREATALBANIANFUTURE", вывод: THEGREATALBANIA
Ссылка на задачу на acm.timus.ru.
Задача 3. Нахождение лексикографически минимального циклического сдвига строки длины n за O(n·log(n))
Дано: Строка S длины до 10^5. Вывести минимальный лексикографически сдвиг строки A.
Пример: Ввод: "program", Вывод: "amprogr"
Задача 4. Сортировка всех циклических сдвигов строки длины n в лексикографическом порядке за O(n·log(n)2)
Дано: Строка S длины до 10^5. Вывести номер позиции исходного слова в отсортированном списке циклических сдвигов. Если таких позиций несколько, то следует вывести позицию с наименьшим номером. Во второй строке вывести последний столбец таблицы циклических сдвигов.
Пример: Ввод: "abraka", Вывод: "2 karaab"
Задача 5. Нахождение количества подпалиндромов строки длины n за O(n·log(n))
Дано: Строка S длины до 10^5. Вывести количество подпалиндромов строки.
Пример: Ввод: "ABACABADABACABA", Вывод: 32
Ссылка на задачу на acmp.ru с ограничениями до 10^5.
Ссылка на задачу на acmp.ru с ограничениями до 10^6.
Задача 6. Количество подстрок строки длины n, являющихся циклическими сдвигами строки длины m за O((n + m)·log(n))
Дано: Заданы две строки S и T длины до 10^5. Необходимо определить, сколько подстрок строки S являются циклическими сдвигами строки T.
Пример: Ввод: S = "aAaa8aaAa", T="aAa", Вывод: 4
Задача 7. Количество суффиксов строки длины n, бесконечное расширение которых совпадает с бесконечным расширением всей строки за O(n·log(n))
Дано: Строка S длины до 10^5. Бесконечным расширением строки назовем строку, полученную выписыванием исходной строки бесконечное число раз. Например, бесконечное расширение строки "abс" равно "abcabcabcabcabc...". Необходимо ответить на вопрос, сколько суффиксов исходной строки имеют такое же бесконечное расширение, какое и строка S.
Пример: На входе: S = "qqqq", на выходе 4.
На этом все. Надеюсь, этот пост поможет Вам активно применять хэширование и решать более сложные задачи. Буду рад любым комментариям, исправлениям и предложениям. В ближайших планах перевести этот пост на английский язык, поэтому нужны ссылки, где эти задачи можно сдать на английском языке. Возможно, к тому времени Вы внесете существенные корректировки и дополнения в этот пост. Ребята из Индии говорят, что пытались сидеть с гугл-переводчиком и переводить с русского языка посты про полиномиальный хэш и у них это плохо вышло. Делитесь другими задачами и, возможно, их решениями, а также решениями указанных задач не через хэши. Спасибо за внимание!
Полезные ссылки:
