Алле очень понравился алгоритм вычисления полиномиального хеша. Помогите ей написать функцию, вычисляющую хеш строки s. В данной задаче необходимо использовать в качестве значений отдельных символов их коды в таблице ASCII.
Полиномиальный хеш считается по формуле:
В первой строке дано число a (1 ≤ a ≤ 1000) –— основание, по которому считается хеш.
Во второй строке дано число m (1 ≤ m ≤ 109) –— модуль.
В третьей строке дана строка s (0 ≤ |s| ≤ 106), состоящая из больших и маленьких латинских букв.
Выведите целое неотрицательное число –— хеш заданной строки.
| Ввод | Вывод |
|---|---|
123 100003 a |
97 |
Гоша написал программу, которая сравнивает строки исключительно по их хешам. Если хеш равен, то и строки равны. Тимофей увидел это безобразие и поручил вам сломать программу Гоши, чтобы остальным неповадно было.
В этой задаче вам надо будет лишь найти две различные строки, которые для заданной хеш-функции будут давать одинаковое значение.
Гоша использует следующую хеш-функцию:
для a = 1000 и m = 123 987 123.
В данной задаче необходимо использовать в качестве значений отдельных символов их коды в таблице ASCII.
В задаче единственный тест без ввода
Алла не остановилась на достигнутом –— теперь она хочет научиться быстро вычислять хеши произвольных подстрок данной строки. Помогите ей!
На вход поступают запросы на подсчёт хешей разных подстрок. Ответ на каждый запрос должен выполняться за O(1). Допустимо в начале работы программы сделать предподсчёт для дальнейшей работы со строкой.
Напомним, что полиномиальный хеш считается по формуле
В данной задаче необходимо использовать в качестве значений отдельных символов их коды в таблице ASCII.
В первой строке дано число a (1 ≤ a ≤ 1000) –— основание, по которому считается хеш. Во второй строке дано число m (1 ≤ m ≤ 107) –— модуль. В третьей строке дана строка s (0 ≤ |s| ≤ 106), состоящая из больших и маленьких латинских букв.
В четвертой строке дано число запросов t –— натуральное число от 1 до 105. В каждой из следующих t строк записаны через пробел два числа l и r –— индексы начала и конца очередной подстроки. (1 ≤ l ≤ r ≤ |s|).
Для каждого запроса выведите на отдельной строке хеш заданной в запросе подстроки.
| Ввод | Вывод |
|---|---|
1000 1000009 abcdefgh 7 1 1 1 5 2 3 3 4 4 4 1 8 5 8 |
97 225076 98099 99100 100 436420 193195 |
В компании, где работает Тимофей, заботятся о досуге сотрудников и устраивают различные кружки по интересам. Когда кто-то записывается на занятие, в лог вносится название кружка.
По записям в логе составьте список всех кружков, в которые ходит хотя бы один человек.
В первой строке даётся натуральное число n, не превосходящее 10 000 –— количество записей в логе.
В следующих n строках —– названия кружков.
Выведите уникальные названия кружков по одному на строке, в порядке появления во входных данных.
| Ввод | Вывод |
|---|---|
8 вышивание крестиком рисование мелками на парте настольный керлинг настольный керлинг кухня африканского племени ужасмай тяжелая атлетика таракановедение таракановедение |
вышивание крестиком рисование мелками на парте настольный керлинг кухня африканского племени ужасмай тяжелая атлетика таракановедение |
На вход подается строка. Нужно определить длину наибольшей подстроки, которая не содержит повторяющиеся символы.
Одна строка, состоящая из строчных латинских букв. Длина строки не превосходит 10 000.
Выведите натуральное число —– ответ на задачу.
| Ввод | Вывод |
|---|---|
abcabcbb |
3 |