Задача

Дана строка $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)

#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;
}

#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)

#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;
}

#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

c-string

Related Images:

Задача

Саша находится в процессе творческого поиска. Она хочет сплести ещё одну фенечку, но испытывает сложности при выборе цветов. Сейчас все $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	+-

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<unsigned long long> t;
vector<unsigned long long> codes;
const unsigned long long prime = 61;
vector<unsigned  long long> pows;

void build (int v, int tl, int tr) {
    if (tl == tr){
        t[v] = codes[tl] * pows[tl - 1];
    }
    else {
        int tm = (tl + tr) / 2;
        build (2 * v, tl, tm);
        build (2 * v + 1, tm + 1, tr);
        t[v] = t[2 * v] + t[2 * v + 1];
    }
}

unsigned long long sum (int v, int tl, int tr, int l, int r) {
    if (l > r){
        return 0;
    }
    if (l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return sum (2 * v, tl, tm, l, min(r, tm))
           + sum (2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
}

void update (int v, int tl, int tr, int pos, unsigned long long newVal) {
    if (tl == tr)
        t[v] = newVal * pows[pos - 1];
    else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update (v*2, tl, tm, pos, newVal);
        else
            update (2 * v + 1, tm + 1, tr, pos, newVal);
        t[v] = t[2 * v] + t[2 * v + 1];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    t.resize(4 * n);
    string a;
    cin >> a;
    codes.resize(n + 1);
    for(int i = 1; i <= n; i++){
        codes[i] = a[i - 1] - 'A' + 1;
    }
    pows.resize(n + 1);
    pows[0] = 1;
    for(int i = 1; i <= n; i++){
        pows[i] = pows[i - 1] * prime;
    }
    build(1, 1, n);
    cin.ignore();
    for(int t = 0; t < k; t++){
        char q;
        cin >> q;
        if(q == '?'){
            int i, j, len;
            cin >> i >> j >>len;
            if(i > j){
                swap(i, j);
            }
            if(sum(1, 1, n, i, i + len - 1) * pows[j - i] == sum(1, 1, n, j, j + len - 1)){
                cout << "+";
            }
            else{
                cout << "-";
            }
        }
        else if(q == '*'){
            int temp;
            char c;
            cin >> temp >> c;
            update(1, 1, n, temp, c - 'A' + 1);
        }
        cin.ignore();
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

vector<unsigned long long> t;

vector<unsigned long long> codes;

const unsigned long long prime = 61;

vector<unsigned long long> pows;

void build (int v, int tl, int tr) {

if (tl == tr){

t[v] = codes[tl] * pows[tl - 1];

}

else {

int tm = (tl + tr) / 2;

build (2 * v, tl, tm);

build (2 * v + 1, tm + 1, tr);

t[v] = t[2 * v] + t[2 * v + 1];

}

unsigned long long sum (int v, int tl, int tr, int l, int r) {

if (l > r){

return 0;

}

if (l == tl && r == tr)

return t[v];

int tm = (tl + tr) / 2;

return sum (2 * v, tl, tm, l, min(r, tm))

+ sum (2 * v + 1, tm + 1, tr, max(l, tm + 1), r);

}

void update (int v, int tl, int tr, int pos, unsigned long long newVal) {

if (tl == tr)

t[v] = newVal * pows[pos - 1];

else {

int tm = (tl + tr) / 2;

if (pos <= tm)

update (v*2, tl, tm, pos, newVal);

else

update (2 * v + 1, tm + 1, tr, pos, newVal);

t[v] = t[2 * v] + t[2 * v + 1];

}

int main() {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int n, k;

cin >> n >> k;

t.resize(4 * n);

string a;

cin >> a;

codes.resize(n + 1);

for(int i = 1; i <= n; i++){

codes[i] = a[i - 1] - 'A' + 1;

}

pows.resize(n + 1);

pows[0] = 1;

for(int i = 1; i <= n; i++){

pows[i] = pows[i - 1] * prime;

}

build(1, 1, n);

cin.ignore();

for(int t = 0; t < k; t++){

char q;

cin >> q;

if(q == '?'){

int i, j, len;

cin >> i >> j >>len;

if(i > j){

swap(i, j);

}

if(sum(1, 1, n, i, i + len - 1) * pows[j - i] == sum(1, 1, n, j, j + len - 1)){

cout << "+";

}

else{

cout << "-";

}

else if(q == '*'){

int temp;

char c;

cin >> temp >> c;

update(1, 1, n, temp, c - 'A' + 1);

}

cin.ignore();

}

return 0;

}

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

Наивный алгоритм тратит на выполнение первого запроса $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

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: равенство подстрок

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

Задача

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

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

Тесты

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

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

Решение

Ссылки

string

c-string

Related Images:

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

Задача

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

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

Тесты

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

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

Ссылки

Related Images: