UPD: while I was translating this post from Russian to English, dacin21 wrote his post, more advanced, link. I hope that my post will help beginners, but in my post more rough estimates.
Hello, codeforces! This blogpost is written for all those who want to understand and use polynomial hashes and learn how to apply them in solving various problems. I will briefly write the theoretical material, consider the features of the implementation and consider some problems, among them:
Searching all occurrences of one string of length n in another string length m in O(n + m) time
Searching for the largest common substring of two strings of lengths n and m (n \ ge m) in O (n + m \ cdot log (m) ^ 2) time $
Finding the lexicographically minimal cyclic shift of a string of length n in O(n cdotlog(n)) time
Sorting of all cyclic shifts of a string of length n in lexicographic order in O(n cdotlog(n)2) time
Finding the number of sub-palindromes of a string of length n in O(n cdotlog(n)) time
The number of substrings of string of length n that are cyclic shifts of the another string length m in O((n + m) cdotlog(n)) time
The number of suffixes of a string of length n, the infinite extension of which coincides with the infinite extension of the given string for O(n cdotlog(n)) ( extension is a duplicate string an infinite number of times).
Note 1. It is possible that some problems can be solved more quickly by other methods, for example, sorting the cyclic shifts & mdash; this is exactly what happens when constructing a suffix array, to search for all occurrences of one string in another will allow the Knut-Morris-Pratt algorithm, the Manaker algorithm works well with the sub-palindromes, and for own suffixes there is a prefix function.
Note 2. In the problems above, an estimate is made when a hash search is performed by sorting and binary searching. If you have your own hash table with open mixing or overflow chains, then you & mdash; lucky, boldly replace the hash search for a search in your hash table, but do not try to use std::unordered_set, as in practice the search in std::unordered_set loses sorting and binary search in connection with the fact that this piece obeys the C++ standard and has to guarantee a lot to the user, which is useful for industrial coding and, often, is useless in the competitive programming, so sorting and binary search for simple structures gain absolute primacy in C++ in speed of work , if not used additional own structures.
Note 3. In cases where comparison of elements is slow (for example, comparison by hash in O(log(n)) time), in the worst case std::random_shuffle + std::sort always loses std::stable_sort, because std::stable_sort guarantees the minimum number of comparisons among all sorts (based on comparisons) for the worst case.
The solution of the listed tasks will be given below, the source codes also.
As advantages of polynomial hashing I can notice that you often do not need to think, you can immediately take and write a naive algorithm to solve the problem and speed it up with polynomial hashing. Personally, firstly, I think about solution with a polynomial hash, perhaps that's why I'm blue.
Among the disadvantages of polynomial hashing: a) Too many operations getting remainder from the integer division, sometimes on the border with TLE for large problems, and b) on the codeforces in C++ programs are often small guarantees against hacking due to MinGW: std::random_device generates the same number every time, std::chrono::high_resolution_clock ticks in microseconds instead of nanoseconds. (The Cygwin compiler for windows wins against MinGW).
What is polynomial hashing?
Hash-function must assign to the object a certain value (hash) and possess the following properties:
If two objects are equal, then their hashes are equal.
If two hashes are equal, then the objects are equal with a high probability.
A collision is the very unpleasant situation of equality of two hashes for not equal objects. Ideally, when you choose a hash function, you need to ensure that probability of collision lowest of possibles. In practice & mdash; just a probability to successfully pass a set of tests to the task.
Consider the sequence a[0], a[1], ..., a[n-1]. Under the polynomial hash for this sequence, we have in mind the result of calculating the following expression:
hash(a, p, m) = (a[0] + a[1] * p + a[2] * p^2 + ... + a[n-1] * p^(n-1)) % m
Here p andm & mdash; point (or base) and a hash module, respectively.
The conditions that we will impose: max(a[i]) < p < m, gcd(p,m) = 1.
Note. If you think about interpreting the expression, then we match the sequences
a[0], a[1], a[2], ..., a[n-1]
number of length n in the number system with base p and take the remainder from its division by the number m, or the value of the polynomial(n-1)-th power with coefficients a [i]at the pointpmodulom. We'll talk about the choice ofpand m` later.
Note. If the value of hash (a, p, m) (not by modulo), is placed in an integer data type (for example, a 64-bit type), then each sequence can be associated with this number. Then the comparison by greater / less / equal can be performed in O(1) time.
Comparison by equal in O(1) time
Now let's answer the question, how to compare arbitrary subsequences for O (1)? We show that to compare the subsequences of the initial sequence a [0], a [1], ..., a [n-1], it is sufficient to compute the polynomial hash on each prefix of the original sequence.
Define a polynomial hash on the prefix as:
pref(k, a, p, m) = (a[0] + a[1] * p + a[2] * p^2 + ... + a[k-1] * p^(k-1)) % m
Briefly denote pref(k, a, p, m) as pref(k) and keep in mind that the final value is taken modulo m. Then:
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, ...
General form:
pref(n) = a[0] + a[1] * p + a[2] * p^2 + ... + a[n-1] * p^(n-1)
The polynomial hash on each prefix can be calculated in O(n) time, using recurrence relations:
p^k = p^(k-1) * p
pref(k+1) = pref(k) + a[k] * p^k
Let's say we need to compare two substrings that begin with i and j and have the length len, for equality:
a[i], a[i+1], ..., a[i+len-1] =? a[j], a[j+1], ..., a[j+len-1]
Consider the differences pref(i + len) - pref(i) and pref(j + len) - pref(j). It's not difficult to see that:
( 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)
We multiply the first equation by p^j, and the second by p^i. We get:
( 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))
We see that on the right-hand side of the expressions in brackets polynomial hashes were obtained from the subsequences:
a[i], a[i+1], ..., a[i+len-1] и a[j], a[j+1], ..., a[j+len-1].
Thus, in order to determine whether the required subsequences have coincided, it is necessary to check the following equality:
p^j * (pref(i+len) - pref(i)) = p^i * (pref(j+len) - pref(j))
One such comparison can be performed in O(1) time, assuming the degree of p modulo precalculated. With the module m, we have:
p^j * (pref(i+len) - pref(i)) % m = p^i * (pref(j+len) - pref(j)) % m
** Cons **: Comparing one line depends on the parameters of the other line (from j).
If we know the maximum lengths of compared lines, then we can apply a different approach. Let's denote the maximum length of compared lines as mxPow. We multiply (I) by mxPow-i-len+1, and (II) to mxPow-j-len+1. We get:
( 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))
We can note that on the right-hand sides of equals a polynomial hash of subsequences. Then, the equality is checked as follows:
p^(mxPow-i-len+1) * (pref(i+len) - pref(i)) % m = p^(mxPow-j-len+1) * (pref(j+len) - pref(j)) % m
This approach allows you to compare ** one substring ** of length len with ** all substrings ** of length len by ** equality **, including ** substrings of another string **, since the expression p^(mxPow-i-len+1) * (pref(i+len)-pref(i)) % m for the substring of the length len starting at the position i, depends only on ** the parameters of the current substring ** i, len and ** constant ** mxPow, and not from the parameters of another substring.
Comparison by greater / less in O(log(n))time
Consider two substrings of (possibly) different strings of lengths len1 andlen2, (len1 <= len2), starting in the positions i andj respectively. Note that the ratio greater / less is determined ** by the first non-equal symbol ** in these substrings, and before this position strings are equal. Thus, we need to find the ** position of the first non-equal symbol ** by the ** binary search method **, and then compare the found symbols. By comparing substrings to equality in O(1) time, we can solve the problem of comparing substrings by greater / less in O(log(len1)) time.
Minimizing the probability of collision
Let for the whole time of the program runs we need to execute nCompChars comparisons of characters. Rough estimation:
nCompChars <= nCompStrings * mxLen^2. Then the probability that the collision will not happens:
p ~=~ 1 - exp(nCompChars / m) ~=~ 1 - exp(nCompStrings * mxLen^2 / m)
Hence it is obvious that m needs to be taken much more than nCompStrings * mxLen ^ 2. Then, approximating the exponential as Taylor series, we get the probability of collision on one test:
p ~=~ 1 - exp(nCompStrings * mxLen^2 / m) ~=~ nCompStrings * mxLen^2 / m
If we look at the problem of searching of occurrences of all cyclic shifts of one row in another string of lengths to 10^5, then we can get 10^15 comparisons of characters (it may seem that 10^20, but the longer the length &mdash , the fewer positions in which you really need to look for matches with the current cyclic shift, so 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.
На этом все. Надеюсь, этот пост поможет Вам активно применять хэширование и решать более сложные задачи. Буду рад любым комментариям, исправлениям и предложениям. В ближайших планах перевести этот пост на английский язык, поэтому нужны ссылки, где эти задачи можно сдать на английском языке. Возможно, к тому времени Вы внесете существенные корректировки и дополнения в этот пост. Ребята из Индии говорят, что пытались сидеть с гугл-переводчиком и переводить с русского языка посты про полиномиальный хэш и у них это плохо вышло. Делитесь другими задачами и, возможно, их решениями, а также решениями указанных задач не через хэши. Спасибо за внимание!
Полезные ссылки:
