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

Related Images:

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

  1. Вы заметили, что задачи этого раздела можно решать с помощью string и char *? Вы можете решить вторым способом и получить оценку еще в одной колонке.
    Теперь по решению. Оно очень «наивное». В том смысле, что можно сделать много более эффективный алгоритм. У Вас 50 тысяч запросов к одной и той же строке. Даже если все эти 50 тысяч запросов будут относиться к одной и той же паре строк, вы будете их снова и снова сравнивать. Разумнее было бы выполнить какую-то предварительную подготовку, проанализировать строку. И дальше быстро отвечать на запросы.
    Подумаете над этим?

    • Хорошо, Игорь Евгеньевич. Я подумаю над этим.

    • Я вообще удивляюсь, как этот код прошел в 2 секунды. Наверно, на сайте нет макстеста.

      Если искать более оптимальное решение, то придется либо «честно» писать суфмассив, либо «нечестно» — хеширование строк.

    • Как ни странно макстест есть. А по количеству тестов (q) они даже в два раза перекрывают собственные ограничения.
      Что касается более быстрого решения через хеши, то одна наша с вами общая знакомая Лена так и решала:

      Вышло очень быстро. Особенно если ускорить ввод вывод.

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