e-olymp 4843. Равные подстроки

Задача

Дана строка $S = s_1 s_2 s_3\cdots s_n$и множество запросов вида $(l_1, r_1, l_2, r_2)$.

Для каждого запроса требуется ответить, равны ли подстроки $s_{l1} … s_{r1}$ и $s_{l2} \cdots s_{r2}$.

Входные данные

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

Выходные данные

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

Тесты

Входные данные Выходные данные
1 abacaba
4
1 1 7 7
1 3 5 7
3 4 4 5
1 7 1 7
++-+
2 qa
3
1 1 1 1
2 2 2 2
1 1 2 2
++-
3 barcarbank
3
2 3 5 6
1 2 7 8
1 3 7 9
++-
4 abbabdad
4
1 3 4 6
2 3 5 6
1 2 4 5
3 5 6 8
—++

Код программы (string)

Код программы (c-string)

Решение

Циклично находим указанные подстроки на введённых отрезках символов и сравниваем их.

Ссылки

string

c-string

e-olymp 5274. Фенечка

Задача

Саша находится в процессе творческого поиска. Она хочет сплести ещё одну фенечку, но испытывает сложности при выборе цветов. Сейчас все $n$ ниток, которые она планирует использовать для плетения, выложены в ряд. В процессе размышления Саша время от времени заменяет нитку одного цвета ниткой другого, а также для проверки того, что узор получается тем, который подразумевается, проверяет, что некоторые последовательности цветов ниток равны.

Напишите программу, которая автоматизирует эти проверки.

Входные данные

В первой строке записаны два целых числа $n$ и $k$ — количество ниток в фенечке и запросов к программе, соответственно $(1 \leq n, k \leq 100000).$ Во второй строке записана строка из $n$ символов — цвета ниток в начальном состоянии. Каждый цвет обозначается строчной или прописной буквой латинского алфавита или цифрой. В следующих $k$ строках заданы запросы двух видов:

«* i c» — заменить нитку с номером $i$ на нитку цвета $c$,
«? i j len» — проверить, равны ли последовательности цветов ниток, начинающиеся в позициях $i$ и $j$ и имеющие длину $len$.

Выходные данные

Для каждого запроса второго вида выведите «+», если последовательности равны, или «-« в противном случае.

Тесты

Входные данные Выходные данные
6 3
abccba
? 2 4 2
* 4 a
? 1 4 2
-+
7 4
abacaba
? 1 5 3
* 6 c
? 2 6 2
? 3 5 3
+-+
8 3
atgthcta
? 2 4 3
* 8 h
? 4 7 2
-+
9 3
abbababba
? 1 6 4
* 2 c
? 1 6 4
+-

Код программы

Решение задачи

Наивный алгоритм тратит на выполнение первого запроса $O\left(1\right)$ единиц времени, а на выполнение запросов второго типа — $O\left(n\right)$ единиц времени. Таким образом получаем ассиптотическую временную сложность $O\left(kn\right),$ из-за чего задача не проходит по времени.
Для сравнения строк будем использовать полиномиальный хеш, зависящий от $p$ (в нашем случае $p = 61$), при этом будем отождествлять равенство хешей по модулю $m$ (в нашем случае $m = 2^{64}$) и самих строк (при этом может случиться так, что хеши будут совпадать, а сами строки — нет, но вероятность достаточно мала и мы будем ею пренебрегать). Таким образом мы получаем возможность сравнивать строки за $O\left(1\right)$ единиц времени. Будем использовать для хранения текущего состояния строки (а точнее ее хеша) дерево отрезков, при этом на нижнем ярусе будем хранить хеши каждого отдельного символа строки с учетом его месторасположения в строке. Таким образом получим возможность выполнять запросы и первого, и второго типов за $O\left(\log{n}\right)$ единиц времени, при этом следует учесть, что хеши двух одинаковых подстрок будут отличаться в $p^{j-i} \mod m$ раз, где $i$ — меньший из индексов начала сравниваемых подстрок, $j$ — больший. Таким образом, получаем итоговую асимптотическую сложность алгоритма $O\left(k\log{n}\right)$

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone