Как найти наибольшую общую подстроку

Задача:

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

Определение:

Будем говорить, что строка является подстрокой строки , если существует такой индекс , что для любого справедливо .

Алгоритм

Пусть длина наибольшей общей подстроки будет . Заметим, что у строк и обязательно найдется общая подстрока длины , так как в качестве такой строки можно взять префикс наибольшей общей подстроки. Рассмотрим предикат , который для из области определения истинен, если у строк и есть общая подстрока длины , иначе ложен. Согласно замечанию, предикат должен по мере возрастания быть истинным до некоторого момента, а затем обращаться в ложь. Собственно, максимальное значение, при котором предикат истинен, является длиной наибольшей общей подстроки. Таким образом, требуется с помощью двоичного поиска найти это значение. В ходе работы придется проверять наличие общей подстроки заданной длины. Для этого будем использовать хеширование, чтобы улучшить асимптотику алгоритма. Алгоритм является эвристическим и может выдавать неверный ответ, так как совпадение хешей строк не гарантирует равенство строк. Поэтому нужно выполнить проверку нескольких случайных символов подстрок на совпадение, проиграв при этом по времени работы. Алгоритм работает следующим образом:

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

• у строки хешируем подстроки заданной длины и в случае совпадения хеша с элементом Set проверяем несколько случайных символов подстрок на совпадение.

Хеширование будем производить так же, как и в алгоритме Рабина-Карпа.

Псевдокод

— длина подстроки, найденная с помощью двоичного поиска.

— предикат, описанный в алгоритме.

bool f(i: int):
  hashes = хеши подстрок строки  длины 
  for j = 0 to |t| − i
    hash = hash(t[j ... j + i − 1])
    if hash in hashes
      if совпали несколько случайных символов подстрок
        return true
      else
        continue
  return false

Время работы

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

См. также

• Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
• Задача о наибольшей общей подпоследовательности

Источники информации

• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 3-е издание. Пер. с англ. — М.:Издательский дом «Вильямс», 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страницы 1036–1041.

I think you can solve this using a pretty elegant dynamic programming algorithm that runs in O(mn) time and O(mn) space, where m and n are the number of characters in each string. The idea is based on the following recurrence. Let the two strings be A = a₀ a₁ a₂ … a_n-1 and B = b₀ b₁ b₂ … b_m-1 and look at their first characters a₀ and b₀. Then there are three ways you can try to find the longest common subsequence:

1. If the first characters are equal, one option would be to find the longest common subsequences of the rest of the two strings, then to prepend the first character to the match.
2. Alternatively, you can decide not to match the first two characters. In that case, one option would be to see what the longest common subsequence you could make while ignoring the first character of the first string.
   3 Finally, you could also ignore the first character of the second string.

This gives us a very nice recurrence:

LCS(A[0 .. n], B[0 .. m]) = longest of {
  A[0] + LCS(A[1 .. n], B[1 .. m])   (if A[0] == B[0]),
         LCS(A[1 .. n], B[0 .. m]),
         LCS(A[0 .. n], B[1 .. m])
    }

As our base cases, the longest common substring of any string and the empty string is the empty string:

LCS (A[n .. n], B[i, m]) = ""
LCS (A[i .. n], B[m, m]) = ""

This definition of the longest common substring allows you to compute the value of LCS(A[i .. n], B[j .. m]) given the three values LCS(A[i + 1 .. n], B[j + 1 .. m]), LCS(A[i .. n], B[j + 1 .. m]), and LCS(A[i + 1 .. n], B[j .. m]). Consequently, if you compute these values in the right order, you can just populate a table with the results in one pass and construct the result from there. Using some standard DP tricks, this can be made to run in O(mn).

Время на прочтение
4 мин

Количество просмотров 21K

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

1. Поделиться со всеми интересным алгоритмом и его реализацией на С++ (стандарт С++11);
2. Узнать, есть ли у данного алгоритма название и/или формальное описание;

Предыстория

Все началось с конкурса, проводимого Intel, о котором я узнал из поста. Суть конкурса сводилась к разработке и реализации алгоритма, решающего задачу нахождения в двух строках максимально длинной общей подстроки (переписывать полностью задачу сюда, думаю, не имеет смысла). К той задачке прилагался референсный код, т.е. решение на которое надо было «равняться». Чуть позже, из форума, посвященному этому конкурсу, стало понятно, что референсный код не решает эту задачу в том виде в котором она сформулирована на сайте Intel. Т.е. весь смысл конкурса сводился к следующему: «сделать программу, которая в точности повторяет вывод референсного кода, при одинаковых входных параметрах, только чтобы она была быстрее и параллельнее».
Ну да ладно, даже несмотря на абсурдность ситуации с описанием задачи, участие в конкурсе я сразу отбросил еще и потому что там могли участвовать только студенты и выпускники. Мне понравилась сама задача, та что описана на сайте.

Постановка задачи

Вот как я понял из описания эту задачу:
Есть две строки S1 и S2, нужно найти максимально длинную общую подстроку(и) (далее будем называть искомые подстроки — подмножествами), длина которой не меньше M. В качестве результата вывести ее координаты.
Координатами являются четыре целых числа.
Первые два относятся к строке S1 — это номера позиций первого и последнего символов найденной подстроки.
Вторые два числа имеют тоже значение, только относятся ко второй строке — S2.

Например, если мы имеем следующие входные параметры:

S1 = ABCCA
S2 = ACCABABCCBAABCBAABCBACBACBACBAC
M = 2

то ответом будет:
0 3 5 8

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

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

Срезюмируем то что нам дается на вход:

1. S1, S2 — две строки, в которых необходимо произвести поиск;
2. M — минимально возможная длина искомой подстроки;
3. K — число потоков которое можно использовать для распаралеливания;

Алгоритм

По сути, идея решения очень проста и состоит из 3-х шагов:

1. Разбить S1 на минимально-возможные (длиной M) сегменты.
2. Спроецировать сегменты на S2.
3. На полученной проекции, найти максимально длинные подмножества (состоящие из максимального количества подряд идущих сегментов).

Рассмотрим работу алгоритма на следующем примере:

S1 = ABCCA
S2 = ACCABABCCBAABCBAABCBACBACBACBAC
M = 2
K = 2

1) Разбиваем S1 на сегменты, каждый длиной M = 2:
AB, BC, CC, CA

2) Проецируем каждый полученный сегмент на S2:

или в виде смещений:

таким образом мы получили проекцию S1 на S2:

дальше будем называть эту проекцию — картой пересечений.

По сути, карта пересечений представляет из себя матрицу координат всех сегментов длина которых равна M. Т.е. каждый элемент матрицы характеризует координату в строке S2, в то время как номер строки матрицы характеризует координату в строке S1. Имея в распоряжении карту пересечений, мы можем найти все пересечения (подмножества) и выбрать из них максимальные.

3) Производим поиск максимальных подмножеств (совокупность сегментов).
Если посмотреть на карту пересечений в символьном виде, то уже визуально можно найти максимально длинное подмножество:

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

т.е. подмножество начинающееся с координаты 5 имеет максимальную длину — len = 4, для подмножества начинающегося с координаты 3 длина будет равна 2 и т.д.

Аналогичным образом, пробегая по каждому сегменту в карте пересечений, мы находим, что максимально длинным подмножеством является подмножество длиной 4 с координатами в S1 и S2 строках: 0 и 5 соответственно.

Распараллеливание

Как можно было заметить каждый шаг в решении этой задачи (шаги 1, 2, 3) легко распараллеливается, возможно применение Map-Reduce.

1, 2) Каждому потоку назначается свой сегмент (или несколько сегментов), для которого он строит проекцию сегмента. В совокупности, после того как для всех сегментов будут получены соответствующие проекции, получим готовую карту пересечений.

3.1) Каждому потоку назначается свой порядковый номер (n). Далее n-ый поток, начиная c n-ой позиции, обрабатывает каждый K-ый элемент карты пересечений. Таким образом мы разбиваем карту пересечений на несколько (число потоков) частей. Из этих частей, выбирают, вышеописанным образом, максимальные подмножества:

3.2) После того как все потоки отработают, мы получим несколько групп подмножеств. Из полученных групп выбираем группы с максимальной длиной сегментов. В нашем примере это две группы: группа образованная потоком #1, содержащая в себе сегменты длиной 3 символа (с начальными координатами: 0; 11 и 1; 6), а также группа образованная потоком #2, содержащая в себе один сегмент длиной 4 символа (с координатами 0; 5). Поскольку вторая группа имеет наибольшую длину сегментов, то первую группу отбрасываем сразу.
В результате мы получили начальные координаты подмножества (0; 5) и его длину — 4. Для нахождения конечных координат применяем формулу: end_coord = start_coord + len — 1.

Таким образом получаем ответ: 0 3 5 8.

Заключение

Я решил не затрагивать рассмотрение деталей реализации, данного алгоритма на С++, так как это уже выходит за рамки данной статьи. Ознакомится с реализацией данного алгоритма на С++ (С++11) можно здесь, для компиляции при помощи GCC не забываем ставить флаги -pthread и -std=с++0X.

Вопрос

Этот алгоритм пришел мне в голову как очевидное решение задачи, но я не знаю, есть ли у него официальное название и/или формальное описание?

Здравствуйте! Этот пост написан для всех тех, кто хочет освоить полиномиальные хэши и научиться применять их в решении различных задач. Я кратко приведу теоретический материал, рассмотрю особенности реализации и разберу некоторые задачи, среди них:

1. Поиск всех вхождений одной строки длины n в другую длины m за O(n + m)

2. Поиск наибольшей общей подстроки двух строк длин n и m (n ≥ m) за O(n + m·log(m)²)

3. Нахождение лексикографически минимального циклического сдвига строки длины n за O(n·log(n))

4. Сортировка всех циклических сдвигов строки длины n в лексикографическом порядке за O(n·log(n)²)

5. Нахождение количества подпалиндромов строки длины n за O(n·log(n))

6. Количество подстрок строки длины n, являющихся циклическими сдвигами строки длины m за O((n + m)·log(n))

7. Количество суффиксов строки длины n, бесконечное расширение которых совпадает с бесконечным расширением всей строки за O(n·log(n)) (расширение — дублирование строки бесконечное число раз)

8. Наибольший общий префикс двух строк длины 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, в том числе и медленного ввода/вывода).

Что такое полиномиальный хэш?

Хэш-функция должна сопоставлять некоторому объекту некоторое число (его хэш) и обладать следующими свойствами:

1. Если два объекта совпадают, то их хэши равны.

2. Если два хэша равны, то объекты совпадают с большой вероятностью.

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

Рассмотрим последовательность {a₀, a₁, …, a_n - 1}. Под полиномиальным хэшем для этой последовательности будем иметь в виду результат вычисления следующего выражения:

Здесь p и m — точка (или основание) и модуль хэширования соответственно.

Условия, которые мы наложим: , .

Примечание. Если подумать об интерпретации выражения, то мы сопоставляем последовательности {a₀, a₁, …, a_n - 1} число длины n в системе счисления p и берем остаток от его деления на число m, или значение многочлена (n - 1)-й степени с коэффициентами a_i в точке p по модулю m. О выборе p и m поговорим позже.

Примечание. Если значение , не взятое по модулю, помещается в целочисленный тип данных (например, 64-битный тип), то можно каждой последовательности сопоставить это число. Тогда сравнение на больше / меньше / равно можно выполнять за O(1).

Сравнение на равенство за O(1)

Теперь ответим на вопрос, как сравнивать произвольные непрерывные подотрезки последовательности за O(1)? Покажем, что для их сравнения достаточно посчитать полиномиальный хэш на каждом префиксе исходной последовательности {a₀, a₁, …, a_n - 1} .

Определим полиномиальный хэш на префиксе как:

Кратко обозначим как и будем иметь в виду, что итоговое значение берется по модулю m. Тогда:

Общий вид:

Полиномиальный хэш на каждом префиксе можно находить за O(n), используя рекуррентные соотношения:

Допустим, нам нужно сравнить две подстроки, начинающиеся в позициях i и j и имеющие длину len, на равенство:

Рассмотрим разности и . Не трудно видеть, что:

Домножим 1-е уравнение на p^j, а 2-е на pⁱ. Получим:

Видим, что в правой части выражений в скобках были получены полиномиальные хэши от подотрезков:

Таким образом, чтобы определить, совпали ли искомые подотрезки, необходимо проверить выполнение следующего равенства:

Одно такое сравнение можно выполнять за O(1), предподсчитав степени p по модулю. С учетом модуля m, имеем:

Проблема: сравнение одной строки зависит от параметров другой строки (от j).

Первое решение данной проблемы основывается на домножении первого уравнения на p^- i, а второго на p^- j. Тогда получим:

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

Для реализации этого необходимо найти обратный элемент для p по модулю m. Из условия gcd(p, m) = 1 обратный элемент всегда существует. Для этого необходимо вычислить значение функции Эйлера для выбранного модуля φ(m) и возвести p в степень φ(m) - 1. Если предподсчитать степени обратного элемента по выбранному модулю, то сравнение можно выполнять за O(1).

Второе решение данной проблемы основывается на знании максимальной длины сравниваемых строк. Обозначим максимальную длину сравниваемых строк как . Домножим 1-е уравнение на p в степени mxPow - i - len + 1, а 2-е на p в степени mxPow - j - len + 1. Тогда:

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

Этот подход позволяет сравнивать одну подстроку длины len со всеми подстроками длины len на равенство, в том числе, и подстроками другой строки, так как выражение для подстроки длины len, начинающейся в позиции i, зависит только от параметров подстроки i, len и константы mxPow, а не от параметров другой подстроки.

Сравнение на больше / меньше за O(log(n))

Рассмотрим две подстроки возможно разных строк длин len1 и len2, (len1 ≤ len2), начинающиеся в позициях i и j соответственно. Заметим, что отношение больше / меньше определяется первым несовпадающим символом в этих подстроках, а до позиции этого символа строки совпадают. Таким образом, необходимо найти позицию первого несовпадающего символа методом бинарного поиска, а затем сравнить найденные символы. Благодаря сравнению подстрок на равенство за O(1), можно решить задачу сравнения подстрок на больше / меньше за O(log(len1)):

Минимизация вероятности коллизии

Пусть за все время работы программы нам нужно выполнить сравнений символов. Грубая оценка:

. Тогда вероятность того, что коллизии не произойдет:

Отсюда очевидно, что m нужно брать значительно больше, чем . Тогда, аппроксимируя экспоненту рядом Тейлора, получаем вероятность коллизии на одном тесте:

Если мы рассмотрим задачу о поиске вхождений всех циклических сдвигов одной строки в другую строку длин до 10⁵, то мы можем получить 10¹⁵ сравнений символов (может показаться, что 10²⁰, но чем больше длина — тем меньше позиций, в которых реально нужно искать совпадения с текущим циклическим сдвигом, поэтому 10¹⁵).

Тогда, если мы возьмем простой модуль порядка 10⁹, то мы не пройдем ни один из максимальных тестов.

Если мы возьмем модуль порядка 10¹⁸, то вероятность коллизии на одном тесте  ≈ 0.001. Если максимальных тестов 100, то вероятность коллизии в одном из тестов  ≈ 0.1, то есть 10%.

Если мы возьмем модуль порядка 10²⁷, то на 100 максимальных тестах вероятность коллизии равна  ≈ 10^- 10.

Вывод: чем больше модуль — тем больше вероятность пройти тест. Эта вероятность не учитывает взломы.

Двойной полиномиальный хэш

Разумеется, в реальных программах мы не можем брать модули порядка 10²⁷. Как быть? На помощь приходит китайская теорема об остатках. Если мы возьмем два взаимно простых модуля m₁ и m₂, то кольцо остатков по модулю m = m₁·m₂ эквивалентно произведению колец по модулям m₁ и m₂, т.е. между ними существует взаимно однозначное соответствие, основанное на идемпотентах кольца вычетов по модулю m. Иными словами, если вычислять по модулю m₁ и по модулю m₂, а затем сравнивать два искомых подотрезка по и одновременно, то это эквивалентно сравнению полиномиальным хэшем по модулю m. Аналогично, можно брать три взаимно простых модуля m₁, m₂, m₃.

Особенности реализации

Итак, мы подошли к реализации описанного выше. Цель — минимум взятий остатка от деления, т.е. получить два умножения в 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.

Ссылка на задачу на acmp.ru.

Задача 2. Поиск наибольшей общей подстроки двух строк длин n и m (n ≥ m) за O(n + m·log(m)²)

Дано: Длина строк 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"

Ссылка на задачу на acmp.ru.

Задача 4. Сортировка всех циклических сдвигов строки длины n в лексикографическом порядке за O(n·log(n)²)

Дано: Строка S длины до 10^5. Вывести номер позиции исходного слова в отсортированном списке циклических сдвигов. Если таких позиций несколько, то следует вывести позицию с наименьшим номером. Во второй строке вывести последний столбец таблицы циклических сдвигов.

Пример: Ввод: "abraka", Вывод: "2 karaab"

Ссылка на задачу на acmp.ru.

Задача 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

Ссылка на задачу на acmp.ru.

Задача 7. Количество суффиксов строки длины n, бесконечное расширение которых совпадает с бесконечным расширением всей строки за O(n·log(n))

Дано: Строка S длины до 10^5. Бесконечным расширением строки назовем строку, полученную выписыванием исходной строки бесконечное число раз. Например, бесконечное расширение строки «abс» равно «abcabcabcabcabc…». Необходимо ответить на вопрос, сколько суффиксов исходной строки имеют такое же бесконечное расширение, какое и строка S.

Пример: На входе: S = "qqqq", на выходе 4.

Ссылка на задачу на acmp.ru.

Задача 8. Наибольший общий префикс двух строк длины n с обменом двух произвольных символов одной строки местами за O(n·log(n))

Дано: Строки S и T длиной до 2*10^5. Разрешается один раз обменять местами два произвольных символа строки S или не менять вовсе. Найти максимальную длину наибольшего общего префикса среди всех возможных замен.

Пример: На входе: S = "aaabaaaaaa" и T = "aaaaaaaaab", на выходе 10.

Ссылка на задачу.

На этом все. Надеюсь, этот пост поможет Вам активно применять хэширование и решать более сложные задачи. Буду рад любым комментариям, исправлениям и предложениям. В ближайших планах перевести этот пост на английский язык, поэтому нужны ссылки, где эти задачи можно сдать на английском языке. Возможно, к тому времени Вы внесете существенные корректировки и дополнения в этот пост. Ребята из Индии говорят, что пытались сидеть с гугл-переводчиком и переводить с русского языка посты про полиномиальный хэш и у них это плохо вышло. Делитесь другими задачами и, возможно, их решениями, а также решениями указанных задач не через хэши. Спасибо за внимание!

Полезные ссылки:

Rolling Hash (Rabin-Karp Algorithm)

Anti-Hash test

Выбор точки хэширования

Anti-Double Hash test

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

На днях отправил резюме в Яндекс.
Откуда мне прислали задание-найти наибольшую общую подстроку. Строк не больше 10, символов в 1 строке не больше 10 000.

Я взял наивный алгоритм. Реализовал реализовал его не совсем так, как в Википедии(эффективнее).

Все отлично, он прошел 14 тестов, везде укладывался в 1 секунду. Но на 15 тесте, Яндекс мне ответил-результат не верен.

Формат входных данных- С начала число строк, потом эти строки.

Не пойму, в чем дело..Яндекс пишет, что все тесты верны. Я искал сторонние решения, и они выдавали мне такой же результат, что и у меня.

Вот 2 решения, которые у меня получились-«bb» и «iq». ..как бы намекая, что iq не достаточно.

И все же.. Это провал в моей логики, или в Яндекс-тестах?

// Яндекс B.cpp: определяет точку входа для консольного приложения.
//

//#include "stdafx.h"
#include <iostream>
#include <string.h>
#include <time.h>

using namespace std;
const int  MAX=10000;
char** _strings=new char*[10];
int len;

char* GetLargestCommonSubstring( char* str1, char* str2 );
inline void readNomberSubstrings();
inline const char* getMaxSubstring();

int main()
{
    readNomberSubstrings();
    cout<< getMaxSubstring();
    return 0;
}

void readNomberSubstrings()
{
    cin>>len;

    for(int i=0; i<len;i++)
        _strings[i]=new char[MAX];

    for(int i=0; i<len; i++)
        cin>>_strings[i];
}

 const char* getMaxSubstring()
{
    char *maxSubstring=_strings[0];
    //long T=clock();
    for(int i=1; i < len; i++)
        maxSubstring=GetLargestCommonSubstring(maxSubstring, _strings[i]);
    //cout<<clock()-T<<endl;
    return maxSubstring;
}

char* GetLargestCommonSubstring( char* str1, char* str2 ) {

    int strLen2=strlen(str2);
    const int solution_size = strLen2+ 1;

    int *x=new int[solution_size]();
    int *y= new int[solution_size]();

    int **previous = &x;
    int **current = &y;

    int max_length = 0;
    int result_index = 0;

    int j;
    int length;
    int J=strLen2 - 1;

    for(int i = strlen(str1) - 1; i >= 0; i--)
    {
        for(j = J; j >= 0; j--) 
        {
            if(str1[i] != str2[j]) 
                (*current)[j] = 0;
            else 
            {
                length = 1 + (*previous)[j + 1];
                if (length > max_length)
                {
                    max_length = length;
                    result_index = i;
                }

                (*current)[j] = length;
            }
        }

        swap(previous, current);
    }
    str1[max_length+result_index]='';
    return &(str1[result_index]);
}