Как называется совпадение хэш кодов двух различных строк
Перейти к содержимому

Как называется совпадение хэш кодов двух различных строк

  • автор:

Хэширование в строковых задачах

Хэш — это какая-то функция, сопоставляющая объектам какого-то множества числовые значения из ограниченного промежутка.

  • Быстро считается — за линейное от размера объекта время;
  • Имеет не очень большие значения — влезающие в 64 бита;
  • «Детерминированно-случайная» — если хэш может принимать \(n\) различных значений, то вероятность того, что хэши от двух случайных объектов совпадут, равна примерно \(\frac\) .

Обычно хэш-функция не является взаимно однозначной: одному хэшу может соответствовать много объектов. Такие функции называют сюръективными.

Для некоторых задач удобнее работать с хэшами, чем с самими объектами. Пусть даны \(n\) строк длины \(m\) , и нас просят \(q\) раз проверять произвольные две на равенство. Вместо наивной проверки за \(O(q \cdot n \cdot m)\) , мы можем посчитать хэши всех строк, сохранить, и во время ответа на запрос сравнивать два числа, а не две строки.

Применения в реальной жизни

  • Чек-суммы. Простой и быстрый способ проверить целостность большого передаваемого файла — посчитать хэш-функцию на стороне отправителя и на стороне получателя и сравнить.
  • Хэш-таблица. Класс unordered_set из STL можно реализовать так: заведём \(n\) изначально пустых односвязных списков. Возьмем какую-нибудь хэш-функцию \(f\) с областью значений \([0, n)\) . При обработке .insert(x) мы будем добавлять элемент \(x\) в \(f(x)\) -тый список. При ответе на .find(x) мы будем проверять, лежит ли \(x\) -тый элемент в \(f(x)\) -том списке. Благодаря «равномерности» хэш-функции, после \(k\) добавлений ожидаемое количество сравнений будет равно \(\frac\) = \(O(1)\) при правильном выборе \(n\) .
  • Мемоизация. В динамическом программировании нам иногда надо работать с состояниями, которые непонятно как кодировать, чтобы «разгладить» в массив. Пример: шахматные позиции. В таком случае нужно писать динамику рекурсивно и хранить подсчитанные значения в хэш-таблице, а для идентификации состояния использовать его хэш.
  • Проверка на изоморфизм. Если нам нужно проверить, что какие-нибудь сложные структуры (например, деревья) совпадают, то мы можем придумать для них хэш-функцию и сравнивать их хэши аналогично примеру со строками.
  • Криптография. Правильнее и безопаснее хранить хэши паролей в базе данных вместо самих паролей — хэш-функцию нельзя однозначно восстановить.
  • Поиск в многомерных пространствах. Детерминированный поиск ближайшей точки среди \(m\) точек в \(n\) -мерном пространстве быстро не решается. Однако можно придумать хэш-функцию, присваивающую лежащим рядом элементам одинаковые хэши, и делать поиск только среди элементов с тем же хэшом, что у запроса.

Хэшируемые объекты могут быть самыми разными: строки, изображения, графы, шахматные позиции, просто битовые файлы.

Сегодня же мы остановимся на строках.

Полиномиальное хэширование

Лайфхак: пока вы не выучили все детерминированные строковые алгоритмы, научитесь пользоваться хэшами.

Будем считать, что строка — это последовательность чисел от \(1\) до \(m\) (размер алфавита). В C++ char это на самом деле тоже число, поэтому можно вычитать из символов минимальный код и кастовать в число: int x = (int) (c — ‘a’ + 1) .

Определим прямой полиномиальный хэш строки как значение следующего многочлена:

\[ h_f = (s_0 + s_1 k + s_2 k^2 + \ldots + s_n k^n) \mod p \]

Здесь \(k\) — произвольное число больше размера алфавита, а \(p\) — достаточно большой модуль, вообще говоря, не обязательно простой.

Его можно посчитать за линейное время, поддерживая переменную, равную нужной в данный момент степени \(k\) :

 const int k = 31, mod = 1e9+7; string s = "abacabadaba"; long long h = 0, m = 1; for (char c : s)  int x = (int) (c - 'a' + 1); h = (h + m * x) % mod; m = (m * k) % mod; >

Можем ещё определить обратный полиномиальный хэш:

\[ h_b = (s_0 k^n + s_1 k^ + \ldots + s_n) \mod p \]

Его преимущество в том, что можно написать на одну строчку кода меньше:

 long long h = 0; for (char c : s)  int x = (int) (c - 'a' + 1); h = (h * k + x) % mod; >

Автору проще думать об обычных многочленах, поэтому он будет везде использовать прямой полиномиальный хэш и обозначать его просто буквой \(h\) .

Зачем это нужно?

Используя тот факт, что хэш это значение многочлена, можно быстро пересчитывать хэш от результата выполнения многих строковых операций.

Например, если нужно посчитать хэш от конкатенации строк \(a\) и \(b\) (т. е. \(b\) приписали в конец строки \(a\) ), то можно просто хэш \(b\) домножить на \(k^<|a|>\) и сложить с хэшом \(a\) :

Удалить префикс строки можно так:

А суффикс — ещё проще:

В задачах нам часто понадобится домножать \(k\) в какой-то степени, поэтому имеет смысл предпосчитать все нужные степени и сохранить в массиве:

 const int maxn = 1e5+5; int p[maxn]; p[0] = 1; for (int i = 1; i  maxn; i++) p[i] = (p[i-1] * k) % mod;

Как это использовать в реальных задачах? Пусть нам надо отвечать на запросы проверки на равенство произвольных подстрок одной большой строки. Подсчитаем значение хэш-функции для каждого префикса:

 int h[maxn]; h[0] = 0; // h[k] -- хэш префикса длины k // будем считать, что s это уже последовательность int-ов for (int i = 0; i  n; i++)  h[i+1] = (h[i] + p[i] * s[i]) % mod;

Теперь с помощью этих префиксных хэшей мы можем определить функцию, которая будет считать хэш на произвольном подотрезке:

Деление по модулю возможно делать только при некоторых k и mod (а именно — при взаимно простых). В любом случае, писать его долго, и мы это делать не хотим.

Для нашей задачи не важно получать именно полиномиальный хэш — главное, чтобы наша функция возвращала одинаковый многочлен от одинаковых подстрок. Вместо приведения к нулевой степени приведём многочлен к какой-нибудь достаточно большой — например, к \(n\) -ной. Так проще — нужно будет домножать, а не делить.

 int hash_substring (int l, int r)  return (h[r+1] - h[l]) * p[n-l] % mod; >

Теперь мы можем просто вызывать эту функцию от двух отрезков и сравнивать числовое значение, отвечая на запрос за \(O(1)\) .

Упражнение. Напишите то же самое, но используя обратный полиномиальный хэш — этот способ тоже имеет право на существование, и местами он даже проще. Обратный хэш подстроки принято считать и использовать в стандартном виде из определения, поскольку там нет необходимости в делении.

Лайфхак. Если взять обратный полиномиальный хэш короткой строки на небольшом алфавите с \(k=10\) , то числовое значение хэша строки будет наглядно соотноситься с самой строкой:

Этим удобно пользоваться при дебаге.

Примеры задач

Количество разных подстрок. Посчитаем хэши от всех подстрок за \(O(n^2)\) и добавим их все в std::set . Чтобы получить ответ, просто вызовем set.size() .

Поиск подстроки в строке. Можно посчитать хэши от шаблона (строки, которую ищем) и пройтись «окном» размера шаблона по тексту, поддерживая хэш текущей подстроки. Если хэш какой-то из этих подстрок совпал с хэшом шаблона, то мы нашли нужную подстроку. Это называется алгоритмом Рабина-Карпа.

Сравнение строк (больше-меньше, а не только равенство). У любых двух строк есть какой-то общий префикс (возможно, пустой). Сделаем бинпоиск по его длине, а дальше сравним два символа, идущие за ним.

Палиндромность подстроки. Можно посчитать два массива — обратные хэши и прямые. Проверка на палиндром будет заключаться в сравнении значений hash_substring() на первом массиве и на втором.

Количество палиндромов. Можно перебрать центр палиндрома, а для каждого центра — бинпоиском его размер. Проверять подстроку на палиндромность мы уже умеем. Как и всегда в задачах на палиндромы, случаи четных и нечетных палиндромов нужно обрабатывать отдельно.

Хранение строк в декартовом дереве

Если для вас всё вышеперечисленное тривиально: можно делать много клёвых вещей, если «оборачивать» строки в декартово дерево. В вершине дерева можно хранить символ, а также хэш подстроки, соответствующей её поддереву. Чтобы поддерживать хэш, нужно просто добавить в upd() пересчёт хэша от конкатенации трёх строк — левого сына, своего собственного символа и правого сына.

Имея такое дерево, мы можем обрабатывать запросы, связанные с изменением строки: удаление и вставка символа, перемещение и переворот подстрок, а если дерево персистентное — то и копирование подстрок. При запросе хэша подстроки нам, как обычно, нужно просто вырезать нужную подстроку и взять хэш, который будет лежать в вершине-корне.

Если нам не нужно обрабатывать запросы вставки и удаления символов, а, например, только изменения, то можно использовать и дерево отрезков вместо декартова.

Вероятность ошибки и почему это всё вообще работает

У алгоритмов, использующих хэширование, есть один неприятный недостаток: недетерминированность. Если мы сгенерируем бесконечное количество примеров, то когда-нибудь нам не повезет, и программа отработает неправильно. На CodeForces даже иногда случаются взломы решений, использующих хэширование — можно в оффлайне сгенерировать тест против конкретного решения.

Событие, когда два хэша совпали, а не должны, называется коллизией. Пусть мы решаем задачу определения количества различных подстрок — мы добавляем в set \(O(n^2)\) различных случайных значений в промежутке \([0, m)\) . Понятно, что если произойдет коллизия, то мы какую-то строку не учтем и получим WA. Насколько большим следует делать \(m\) , чтобы не бояться такого?

Выбор констант

Практическое правило: если вам нужно хранить \(n\) различных хэшей, то безопасный модуль — это число порядка \(10 \cdot n^2\) . Обоснование — см. парадокс дней рождений.

Не всегда такой можно выбрать один — если он будет слишком большой, будут происходить переполнения. Вместо этого можно брать два или даже три модуля и считать много хэшей параллельно.

Можно также брать модуль \(2^\) . У него есть несколько преимуществ:

  • Он большой — второй модуль точно не понадобится.
  • С ним ни о каких переполнениях заботиться не нужно — если все хранить в unsigned long long , процессор сам автоматически сделает эти взятия остатков при переполнении.
  • С ним хэширование будет быстрее — раз переполнение происходит на уровне процессора, можно не выполнять долгую операцию % .

Всё с этим модулем было прекрасно, пока не придумали тест против него. Однако, его добавляют далеко не на все контесты — имейте это в виду.

В выборе же \(k\) ограничения не такие серьезные:

  • Она должна быть чуть больше размера словаря — иначе можно изменить две соседние буквы и получить коллизию.
  • Она должна быть взаимно проста с модулем — иначе в какой-то момент всё может занулиться.

Главное — чтобы значения \(k\) и модуля не знал человек, который генерирует тесты.

Парадокс дней рождений

В группе, состоящей из 23 или более человек, вероятность совпадения дней рождения хотя бы у двух людей превышает 50%.

Более общее утверждение: в мультимножество нужно добавить \(\Theta(\sqrt)\) случайных чисел от 1 до n, чтобы какие-то два совпали.

Первое доказательство (для любителей матана). Пусть \(f(n, d)\) это вероятность того, что в группе из \(n\) человек ни у кого не совпали дни рождения. Будем считать, что дни рождения распределены независимо и равномерно в промежутке от \(1\) до \(d\) .

\[ f(n, d) = (1-\frac) \times (1-\frac) \times . \times (1-\frac) \]

Попытаемся оценить \(f\) :

Из последнего выражения более-менее понятно, что вероятность \(\frac\) достигается при \(n \approx \sqrt\) и в этой точке изменяется очень быстро.

Второе доказательство (для любителей теорвера). Введем \(\frac\) индикаторов — по одному для каждой пары людей \((i, j)\) — каждый будет равен единице, если дни рождения совпали. Ожидание и вероятность каждого индикатора равна \(\frac\) .

Обозначим за \(X\) число совпавших дней рождений. Его ожидание равно сумме ожиданий этих индикаторов, то есть \(\frac \cdot \frac\) .

Отсюда понятно, что если \(d = \Theta(n^2)\) , то ожидание равно константе, а если \(d\) асимптотически больше или меньше, то \(X\) стремится нулю или бесконечности соответственно.

Примечание: формально, из этого явно не следует, что вероятности тоже стремятся к 0 и 1.

Бонус: «мета-задача»

Дана произвольная строка, по которой известным только авторам задачи способом генерируется ответ yes/no. В задаче 100 тестов. У вас есть 20 попыток отослать решение. В качестве фидбэка вам доступны вердикты на каждом тесте. Вердиктов всего два: OK (ответ совпал) и WA. Попытки поделить на ноль, выделить терабайт памяти и подобное тоже считаются как WA.

Почему одинаковый хэш-код может быть у разных объектов?

Иначе наши методы будут лишены смысла. Проверка по hashCode(), как мы и сказали, должна идти первой для повышения быстродействия. Если хэш-коды будут разными, проверка вернет false, хотя объекты на самом деле равны (согласно нашему определению в методе equals()).

Если метод hashCode() вызывается несколько раз на одном и том же объекте, каждый раз он должен возвращать одно и то же число.

Правило 1 не работает в обратную сторону. Одинаковый хэш-код может быть у двух разных объектов.

Я запутался помогите разобраться:
Почему в 3 правило написано мол правило 1 не работает в обратную сторону?
Получается 1 правило 2 объекта равны и у них хэш-код одинаковый.
А 3 правило так же одинаковый хэш-код у 2 объектов или я не очень понимаю? Почему в 1 правило написано если 2 объекта равны, а в 3 правило написано одинаковый хэш-код может быть у двух РАЗНЫХ объектов, как понять разных?

Отслеживать
66.6k 6 6 золотых знаков 54 54 серебряных знака 113 113 бронзовых знаков
задан 11 мая 2019 в 9:38
Петровченко Иван Петровченко Иван
1,913 1 1 золотой знак 13 13 серебряных знаков 39 39 бронзовых знаков

Вся суть в том, что множество объектов ограничено только Вашей фантазией, а множество хэш-кодов ограничено диапазоном типа Integer . Исходя из этого, кол-во различных объектов может быть больше, чем кол-во различных хэш-кодов, откуда следует, что у разных объектов может быть одинаковый хэш-код (т.н. коллизия). Сначала проверяется хэш-код, а затем equals . Если хэш-коды разные, то и объекты гарантированно разные и проверять на equals смысла нет. Если же хэш-коды одинаковые, то необходимо еще проверить на equals .

11 мая 2019 в 9:52
@post_zeew а если использовать BigInteger ?)
11 мая 2019 в 9:56

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Примечание: предполагается, что в классе переопределен метод hashCode() .

По хорошему, у разных объектов хешкод должен быть разный. Но на практике иногда происходит по другому. Очень часто это происходит из-за несовершенства формулы для вычисления хешкода.

Пример: хеш строки считается по длине строки: length*3 . Тогда у строк foo и bar одинаковые хеши.

Вообще, хешкод используется для того, чтобы можно было точно сказать, что объекты разные. Но не для того, чтобы сказать, что они одинаковые. Одинаковый хешкод — не гарантия одинаковых объектов.

Обычно он используется для сравнения объектов:
Допустим, у вас есть объект, в котором есть много-много полей. В большинстве случаев объекты для сравнения будут неравны. Чтобы не сравнивать кучу переменных(если объекты не равны), можно сначала сравнивать хешкод(т.к., если хеш различается, то объекты точно различны). Если хеши отличаются — можно дальше не сравнивать переменные. Если одинаковы — дальше нужно сравнить переменные(т.к., если хеши одинаковы, то это не значит, что объекты одинаковы).

Ну и последнее — почти всегда возвращаемый тип метода hashCode() — int . У int есть определенный предел(от -21. до +21. если я не ошибаюсь). Если разных объектов будет больше, чем этот предел, то физически нельзя сгенерировать разные хеши для всех объектов. Т.е., при использовании хешей можно увеличить производительность программы.

Попробую объяснить правила:

  • У одинаковых объектов всегда одинаковые хеши
  • У одного и того же объекта всегда должен быть неизменяемый хешкод(если значения внутри объекта не изменились)
  • У разных объектов иногда могут быть одинаковые хеши

Как называется совпадение хэш кодов двух различных строк

Почему я могу вызвать model.hashCode() из метода hashCode, но не могу это сделать из метода main подскажите?

Максим Li Уровень 36
29 марта 2024
Хорошая статья
Silver2024 Уровень 17
29 февраля 2024
Супер! Спасибо за статью
Ислам Уровень 33
23 февраля 2024
Прекрасная статья
Алимгулов Расим Уровень 45
5 февраля 2024
Спасибо за статью, довольно понятно.
Stanislav Уровень 15
24 декабря 2023
Рин Уровень 39
14 декабря 2023

Хочу заметить, что во всех приведенных здесь примерах не соблюден принцип неизменяемости Проще говоря, возьмем мы человека, присвоим ему днк код, положим в мапку. Изменим ему днк код. И все) Методом get() мы его из мапки уже не достанем, потому что хэшкод изменился, и по новому «адресу» этот человек не живет) Поэтому hashCode() и equals() нужно завязывать на неизменяемые переменные

Anonymous #2664456 Уровень 13
28 ноября 2023

Это шикарная статья, почему то именно это мне тяжело было понять. Благодарю. Но я по прежнему не понимаю зачем даункастить (Man ) o, попозже перечитаю еще может я что то пропустила.

Денис Черемных Уровень 26
17 октября 2023

Хотелось бы дополнить, что при переопределении метода equals, при сравнении параметров обязательна проверка на null, если параметры строковые (или иной другой объект). Без проверки может быть выброшена ошибка, если мы пытаемся сравнить null с другой строкой.

Полиномиальные хеши и их применение

Здравствуй, хабр. Сегодня я напишу, как можно использовать полиномиальные хеши (далее просто хеши) при решении различных алгоритмических задач.

Введение

Начнем с определения. Пусть у нас есть строка s0..n-1. Полиномиальным хешем этой строки называется число h = hash(s0..n-1) = s0 + ps1 + p 2 s2 +… + p n-1 sn-1, где p — некоторое натуральное число (позже будет сказано, какое именно), а si — код i-ого символа строки s (почти во всех современных языках он записывается s[i] ).

Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны. Поэтому основная операция, которую позволяют выполнять хеши — быстрое сравнение двух подстрок на равенство. Конечно, чтобы сравнить 2 строки, мы можем написать подобную функцию (будем считать, что длины строк s и t совпадают и равны n):

boolean equals(char[] s, char[] t) < for (int i = 0; i < n; i++) if (s[i] != t[i]) < return false; >> return true; > 

Однако в худшем случае эта функция обязана проверить все символы, что дает асимптотику O(n).

Сравнение строк с помощью хешей

Теперь посмотрим, как справляются с этой задачей хеши. Так как хеш — это всего лишь число, для их сравнения нам потребуется O(1) времени. Правда, для того, чтобы посчитать хеш одной подстроки наивным способом, требуется O(n) времени. Поэтому потребуется немного повозиться с математическими формулами и научиться находить за O(n) хеши сразу всех подстрок. Давайте сравним подстроки sL..R и tX..Y (одинаковой длины). Пользуясь определением хеша, мы можем записать:

Проведем небольшие преобразования в левой части (в правой части все будет происходить аналогично). Запишем хеш подстроки s0..R, он нам понадобится:

Разобьем это выражение на две части…

… и вынесем из второй скобки множитель p L :

Выражение в первой скобке есть не что иное, как хеш подстроки s0..L-1, а во второй — хеш нужной нам подстроки sL..R. Итак, мы получили, что:

Отсюда вытекает следующая формула для hash(sL..R):

Аналогично, для второй нашей подстроки будет выполнено равенство hash(tX..Y) = (1 / p X )(hash(t0..Y) — hash(t0..X-1)).

Внимательно глядя на эти формулы, можно заметить, что для вычисления хеша любой подстроки нам необходимо знать лишь хеши префиксов этой строки s0..0, s0..1, . s0..n-2, s0..n-1. А, так как хеш каждого следующего префикса выражается через хеш предыдущего, их несложно посчитать линейным проходом по строке. Все сразу за O(n) времени. Степени числа p тоже надо заранее предпросчитать и сохранить в массиве.

// сохраняем в массиве степени числа p, которые нам могут понадобиться pow[0] = 1; for (int i = 1; i // считаем хеши префиксов строки s hs[0] = s[0]; for (int i = 1; i < n; i++) < hs[i] = hs[i - 1] + pow[i] * s[i]; >// считаем хеши префиксов строки t ht[0] = t[0]; for (int i = 1; i

Казалось бы, мы теперь во всеоружии и умеем сравнивать 2 любые подстроки за O(1). Но не все так просто: математические формулы нуждаются в некоторой доработке. К примеру, подобный код:

if ((hs[R] - hs[L - 1]) / pow[L] == (ht[Y] - ht[X - 1]) / pow[X])
    Замечание первое: L (или X) может оказаться равным нулю, и при вычислении hs[L — 1] произойдет выход за границы массива. Однако если L равно нулю, то интересующий нас хеш подстроки sL..R хранится в точности в hs[R] . Поэтому правильнее вместо hs[L — 1] писать так:
L == 0 ? 0 : hs[L - 1]
if ((hs[R] - (L == 0 ? 0 : hs[L - 1])) * pow[X] == (ht[Y] - (X == 0 ? 0 : ht[X - 1])) * pow[L])
Задачи, решаемые с помощью хешей
1. Сравнение подстрок

Первое, и главное, применение, как уже было сказано, это быстрое сравнение двух подстрок — на нем основываются все остальные алгоритмы с хешами. Код в прошлом разделе довольно громоздкий, поэтому я напишу более удобный код, который будет использоваться в дальнейшем.
Следующая функция вычисляет хеш подстроки sL..R, умноженный на p L :

long getHash(long[] h, int L, int R) < long result = h[R]; if (L >0) result -= h[L - 1]; return result; > 

Теперь сравнение двух подстрок мы выполняем следующей строчкой:

if (getHash(hs, L, R) * pow[X] == getHash(ht, X, Y) * pow[L])

Умножение на степени числа p можно назвать «приведением к одной степени». Первый хеш был умножен на p L , а второй — на p X — значит, чтобы сравнение происходило корректно, их надо домножить на недостающий множитель.
Примечание: имеет смысл сначала проверить, совпадают ли длины подстрок. Если нет, то строки в принципе не могут быть равны, и тогда можно не проверять вышезаписанное условие.

2. Поиск подстроки в строке за O(n + m)

Хеши позволяют искать подстроку в строке за асимптотически минимальное время. Это делает так называемый алгоритм Рабина-Карпа.
Пусть есть строка s длины n, в которой мы хотим найти все вхождения строки t длины m. Найдем хеш строки t (всей строки целиком) и хеши всех префиксов строки s, а затем будем двигаться по строке s окном длины m, сравнивая подстроки si..i+m-1.
Код:

// считаем хеш строки t long ht = t[0]; for (int i = 1; i < m; i++) < ht += pow[i] * t[i]; >// проверяем все позиции for (int i = 0; i + m > 
3. Нахождение z-функции за O(n log n)

Z-функцией строки s называется массив z, i-ый элемент которого равен наидлиннейшему префиксу подстроки, начинающейся с позиции i в строке s, который одновременно является и префиксом всей строки s. Значение z-функции в нулевой позиции будем считать равным длине строки s, хотя некоторые источники принимают его за ноль (но это не критично).

Конечно, есть алгоритм нахождения z-функции за O(n). Но когда его не знаешь или не помнишь (а алгоритм довольно громоздкий), на помощь приходят хеши.

Идея следующая: для каждого i = 0, 1, . n-1 будем искать zi бинарным поиском, т.е. на каждой итерации сокращая интервал возможных значений вдвое. Это корректно, потому что равенство s0..k-1 = si..i+k-1 обязательно выполняется для всех k, меньших zi, и обязательно не выполняется для больших k.

int[] z = new int[n]; for (int i = 0; i < n; i++) < int left = 1, right = n - i; // текущий интервал значений while (left else < // если не совпадают, надо проверить меньшие значения right = middle - 1; >> > 
4. Поиск лексикографически минимального циклического сдвига строки за O(n log n).

Существует алгоритм Дюваля, который позволяет решать эту задачу за O(n), однако я знаю некоторых довольно сильных олимпиадных программистов, которые так и не разобрались в нем. Пока они будут в нем разбираться, мы снова применим хеши.

Алгоритм следующий. Сначала примем саму строку s за лучший (лексикографически минимальный) ответ. Затем для каждого циклического сдвига с помощью бинарного поиска найдем длину максимального общего префикса этого сдвига и текущего лучшего ответа. После этого достаточно сравнить следующие за этим префиксом символы и, если надо, обновить ответ.
Еще заметим, что для удобства здесь рекомендуется приписать строку s к самой себе — не придется делать операции взятия по модулю при обращениям к символам строки s. Будем считать, что это уже сделано.

int bestPos = 0; for (int i = 1; i < n; i++) < int left = 1, right = n, length = 0; // находим length - длину максимального общего префикса while (left else < right = middle - 1; >> // сравниваем следующий за общим префиксом символ и обновляем ответ // если длина этого префикса равна n, // то текущий циклический сдвиг совпадает с минимальным, // и ответ обновлять не нужно if (length < n && s[i + length] < s[bestPos + length]) < bestPos = i; >> 

Примечание: по сути, внутри цикла for написан компаратор, сравнивающий лексикографически два циклических сдвига. Используя его, можно за O(n log 2 n) отсортировать все циклические сдвиги.

5. Поиск всех палиндромов в строке за O(n log n).

Опять же, существует решение этой задачи за O(n). И опять мы будем решать ее с помощью хешей.

Подстрока sL..R называется палиндромом, если sL = sR, sL+1 = sR-1, и т.д. Если выражаться русским языком, то это означает, что она читается одинаково как слева направо, так и справа налево.

Возможно, вы уже знаете или догадались, при чем тут хеши. Помимо массива h[] , содержащего хеши для подстрок s0..0, s0..1, . s0..n-2, s0..n-1, посчитаем второй массив rh[] (для «перевернутой» строки), который будем обходить справа налево. Он будет содержать соответственно хеши s0..n-1, s1..n-1, . sn-2..n-1, sn-1..n-1:

rh[n - 1] = s[n - 1]; for (int i = n - 2, j = 1; i >= 0; i--, j++)

Должно уже быть понятно, как за O(1) определять, является ли строка палиндромом. Я напишу функцию getRevHash(), аналогичную getHash(), а потом приведу необходимое условие сравнения. Вы можете самостоятельно убедиться в правильности этого выражения, проделав математические выкладки, подобные тем, что приводились в начале статьи.

long getRevHash(long[] rh, int L, int R) < long result = rh[L]; if (R < n - 1) result -= rh[R + 1]; return result; >boolean isPalindrome(long[] h, long[] rh, long[] pow, int L, int R)

Теперь рассмотрим позицию i в строке. Пусть существует палиндром нечетной длины d с центром в позиции i (в случае четной длины — с центром между позициями i-1 и i). Если обрезать с его краев по одному символу, он останется палиндромом. И так можно продолжать, пока его длина не станет равной нулю.
Таким образом, нам достаточно для каждой позиции хранить 2 значения: сколько существует палиндромов нечетной длины с центром в позиции i, и сколько существует палиндромов четной длины с центром между позициями i-1 и i. Обратите внимание, что эти 2 значения абсолютно независимы друг от друга, и обрабатывать их надо отдельно.

Применим, как и ранее, бинарный поиск:

int[] oddCount = new int[n]; for (int i = 0; i < n; i++) < int left = 1, right = min(i + 1, n - i); while (left else < right = middle - 1; >> > int[] evenCount = new int[n]; for (int i = 0; i < n; i++) < int left = 1, right = min(i, n - i); while (left else < right = middle - 1; >> > 

Теперь можно, к примеру, найти общее количество всех палиндромов в строке, или длину максимального палиндрома. Длина максимального нечетного палиндрома с центром в позиции i считается как 2 * oddCount[i] — 1 , а максимального четного палиндрома — 2 * evenCount[i] .
Еще раз напомню, что нужно быть внимательнее с палиндромами четной и нечетной длины — как правило, их надо обрабатывать независимо друг от друга.

Хеши в матрицах

Наконец, рассмотрим более изощренные применения хешей. Теперь наше пространство будет двумерным, и сравнивать мы будем подматрицы. К счастью, хеши очень хорошо обобщаются на двумерный случай (трехмерных и более я не встречал).

Теперь вместо числа p и массива pow у нас будут два различных числа p, q и два массива pow1 , pow2 : по одному числу и по одному массиву в каждом направлении: по вертикали и горизонтали.

Хешем матрицы a0..n-1, 0..m-1 будем называть сумму по всем i = 0, . n-1, j = 0. m-1 величин p i q j aij.

Теперь научимся считать хеши подматриц, содержащих левый верхний элемент a00. Очевидно, что hash(a0..0, 0..0) = a00. Почти так же очевидно, что для всех j = 1. m-1 hash(a0..0, 0..j) = hash(a0..0, 0..j-1) + q j a0j, для всех i = 1. n-1 hash(a0..i, 0..0) = hash(a0..i-1, 0..0) + p i ai0. Это напрямую вытекает из одномерного случая.

Как посчитать хеш подматрицы a0..i, 0..j? Можно догадаться, что hash(a0..i, 0..j) = hash(a0..i-1, 0..j) + hash(a0..i, 0..j-1) — hash(a0..i-1, 0..j-1) + p i q j aij. Эту формулу можно получить из следующих соображений: сложим все слагаемые (хеш, напомню, это сумма нескольких слагаемых), составляющие хеш подматриц a0..i-1, 0..j и a0..i, 0..j-1. При этом мы два раза учли слагаемые, составляющие подматрицу a0..i-1, 0..j-1, так что вычтем их, чтобы они учитывались один раз. Теперь не хватает только элемента aij, умноженного на соответствующие степени p и q.

Примерно из тех же соображений, что и в первой части статьи (вы уже заметили причастность формулы включений-исключений?) строится функция для вычисления хеша произвольной подматрицы ax1..x2, y1..y2:

long getMatrixHash(long[][] h, int x1, int x2, int y1, int y2) < long result = h[x2][y2]; if (x1 >0) result -= h[x1 - 1][y2]; if (y1 > 0) result -= h[x2][y1 - 1]; if (x1 > 0 && y1 > 0) result += h[x1 - 1][y1 - 1]; return result; > 

Эта функция возвращает хеш подматрицы ax1..x2, y1..y2, умноженный на величину p x1 q y1 .

А сравнение двух подматриц aax1..ax2, ay1..ay2 и abx1..bx2, by1..by2 выполняется с помощью следующего выражения:

if (getMatrixHash(h, ax1, ax2, ay1, ay2) * pow1[bx1] * pow2[by1] == getMatrixHash(h, bx1, bx2, by1, by2) * pow1[ax1] * pow2[ay1])

Хешами также можно решать задачи, связанные с нахождением самой большой симметричной подматрицы и похожие на них. Причем я не знаю сравнимых с хешами по скорости и простоте алгоритмов, выполняющих эту работу. Здесь используются те же принципы, что и при поиске палиндромов в одномерном случае (т.е. считать «реверснутые» хеши справа налево и снизу вверх, проводить бинпоиск отдельно для подматриц четной и нечетной длины). Предлагаю попробовать решить эту задачу самостоятельно — эта статья вам поможет!

Заключение

Итак, в нашем распоряжении есть довольно неплохой аппарат, позволяющий делать многие вещи либо с лучшей возможной асимптотикой, либо лишь чуть-чуть (в логарифм раз) медленнее, чем специализированные алгоритмы. Неплохо, не так ли?

  • алгоритмы
  • олимпиадные задачи
  • хеширование
  • строки
  • поиск подстроки в строке
  • сравнение строк

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *