Хеширование

Упражнения

Ввод-вывод во всех задачах может быть как стандартным, так и файловым.

A: Равные подстроки

Дана строка \(S = s_1s_2 \ldots s_n\) (индексация символов подстроки начинается с числа 1!) и множество запросов вида (\(l_1, r_1, l_2, r_2\)). Для каждого такого запроса нужно ответить, равны ли подстроки \(s_{l_1} \ldots s_{r_1}\) и \(s_{l_2} \ldots s_{r_2}\).

В первой строке записана строка \(S\), состоящая из строчных латинских букв. Эта строка непустая и имеет длину не более \(100\,000\) символов. Во второй строке записано целое число \(q\) (\(1 \le q \le 100\,000\)) — количество запросов. В каждой из следующих \(q\) строк записаны числа \(l_1, r_1, l_2, r_2\) (\(1 \le l_1 \le r_1 \le |S|\); \(1 \le l_2 \le r_2 \le |S|\)).

Для каждого запроса выведите “+”, если соответствующие подстроки равны, и “-” в противном случае.

abacaba
4
1 1 7 7
1 3 5 7
3 4 4 5
1 7 1 7

++-+

B: Поиск общей подстроки

Даны две строки \(A\) и \(B\). Так же дано число \(L\). Нужно узнать, есть ли у строк \(A\) и \(B\) общая подстрока длиной \(L\).

В первых двух строках записаны строки \(A\) и \(B\), состоящие из строчных латинских букв. Эти строки непустые и имеют длину не более \(100\,000\) символов. В третьей строке записано целое число \(L\) (\(0 \le L \le 100\,000\)) — длина общей подстроки.

Выведите YES, если существует общая подстрока такой длины. В противном случае выведите NO.

saaa
baaa
3

YES

raabc
taaac
3

NO

C: Наибольшая общая подстрока

Даны две строки. Найдите длину их максимальной общей подстроки.

В первых двух строках записаны строки \(A\) и \(B\), состоящие из строчных латинских букв. Эти строки непустые и имеют длину не более \(30\,000\) символов.

Выведите длину их максимальной общей подстроки.

abacaba
acabaca

5

abc
xyz

aaa
aaa

3

aabc
aaac

2

D: Циклический палиндром

Дана строка из маленьких латинских букв. Найдите её циклический сдвиг, являющийся палиндромом или установите, что такого нет.

Дана непустая строка длиной до $100000$ символов, состоящая из маленьких латинских букв.

Если искомый циклический сдвиг есть, то выведите номер его первого символа (индексация начинается с 1). Если циклических сдвигов несколько, то выведите любой. Если его нет, то выведите -1.

aaa

1

bba

2

abc

-1

E: Наибольшая общая подстрока - 2

Даны \(K\) строк из маленьких латинских букв. Требуется найти их наибольшую общую подстроку.

В первой строке дано число \(K\) (\(1 \le K \le 10\)). В следующих \(K\) строках — собственно \(K\) строк (длины строк от \(1\) до \(10\,000\)).

Выведите наибольшую общую подстроку данных строк.

3
abacaba
mycabarchive
acabistrue

cab