Задача
Дана строка $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)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> #include <string> using namespace std; int main() { string s; int q, begin1, end1, begin2, end2; getline(cin, s); cin >> q; while (q--) { cin >> begin1 >> end1 >> begin2 >> end2; end1 -= --begin1; // в begin1/2 останется индекс начала подстроки end2 -= --begin2; // в end1/2 - кол-во последующих букв cout << (s.substr(begin1, end1) == s.substr(begin2, end2) ? '+' : '-'); } return 0; } |
Код программы (c-string)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> #include <cstring> using namespace std; int main() { char str[100001], substr1[100001], substr2[100001]; cin >> str; int q, l1, r1, l2, r2; cin >> q; while (q--) { cin >> l1 >> r1 >> l2 >> r2; strncpy(substr1, &str[l1 - 1], r1 - l1 + 1); strncpy(substr2, &str[l2 - 1], r2 - l2 + 1); cout <<( strcmp(substr1,substr2) == 0 ? '+': '-'); memset(substr1, 0, sizeof(substr1)/sizeof(substr1[0])); memset(substr2, 0, sizeof(substr2)/sizeof(substr2[0])); } return 0; } |
Решение
Циклично находим указанные подстроки на введённых отрезках символов и сравниваем их.
Вы заметили, что задачи этого раздела можно решать с помощью string и char *? Вы можете решить вторым способом и получить оценку еще в одной колонке.
Теперь по решению. Оно очень «наивное». В том смысле, что можно сделать много более эффективный алгоритм. У Вас 50 тысяч запросов к одной и той же строке. Даже если все эти 50 тысяч запросов будут относиться к одной и той же паре строк, вы будете их снова и снова сравнивать. Разумнее было бы выполнить какую-то предварительную подготовку, проанализировать строку. И дальше быстро отвечать на запросы.
Подумаете над этим?
Хорошо, Игорь Евгеньевич. Я подумаю над этим.
Я вообще удивляюсь, как этот код прошел в 2 секунды. Наверно, на сайте нет макстеста.
Если искать более оптимальное решение, то придется либо «честно» писать суфмассив, либо «нечестно» — хеширование строк.
Как ни странно макстест есть. А по количеству тестов (q) они даже в два раза перекрывают собственные ограничения.
Что касается более быстрого решения через хеши, то одна наша с вами общая знакомая Лена так и решала:
Вышло очень быстро. Особенно если ускорить ввод вывод.