Задача

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

Найдите максимально возможную длину полученного слова.

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

Каждый тест состоит из одной строки, содержащей два заданных слова, разделенных пробелом. Длина каждого слова от $1$ до $200$ символов. Всего имеется не более $10$ тестов.

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

Для каждого теста выведите максимально возможную длину полученных одинаковых слов (длину максимального слова, которое можно получить путем удаления некоторых букв). Если одинаковые слова получить невозможно, то выведите $0$.

Тесты

Входные данные	Выходные данные
AAABBB ABABAB AXYAAZ CCCXCCCYCCCZCC	4 3
AAAAA BBBBB	0
ABABA BCACB	3
STRING GNIRTS	1

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

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

AAABBB ABABAB
AXYAAZ CCCXCCCYCCCZCC

4
3

AAAAA BBBBB

ABABA BCACB

STRING GNIRTS

String

#include <iostream>
 
using namespace std;
 
int main() {
    string x, y;
    int A[2][1001];
    while (cin >> x  >> y ) 
    {
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 1001; j++){
                A[i][j] = 0;        
            }
        }
        for (int i = 0; i < x.size(); i++){
            for (int j = 0; j < y.size(); j++){
                if (x[i] == y[j]) A[i % 2][(j + 1)] = 1 + A[(i + 1) % 2][j];
                else A[i % 2][j + 1] = max(A[(i + 1) % 2][j + 1], A[i % 2][j]);
            }
        }
        cout <<  A[(x.size() + 1) % 2][y.size()] << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string x, y;

int A[2][1001];

while (cin >> x >> y )

{

for (int i = 0; i < 2; i++){

for (int j = 0; j < 1001; j++){

A[i][j] = 0;

}

for (int i = 0; i < x.size(); i++){

for (int j = 0; j < y.size(); j++){

if (x[i] == y[j]) A[i % 2][(j + 1)] = 1 + A[(i + 1) % 2][j];

else A[i % 2][j + 1] = max(A[(i + 1) % 2][j + 1], A[i % 2][j]);

}

cout << A[(x.size() + 1) % 2][y.size()] << endl;

}

return 0;

}

C-String

#include <iostream>
#include <cstring>
 
using namespace std;
 
int main() {
    string x, y;
    int A[2][1001];
    while (cin >> x  >> y ) 
    {
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 1001; j++){
                A[i][j] = 0;        
            }
        }
        for (int i = 0; i < x.length(); i++){
            for (int j = 0; j < y.length(); j++){
                if (x[i] == y[j]) A[i % 2][(j + 1)] = 1 + A[(i + 1) % 2][j];
                else A[i % 2][j + 1] = max(A[(i + 1) % 2][j + 1], A[i % 2][j]);
            }
        }
        cout <<  A[(x.length() + 1) % 2][y.length()] << endl;
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

string x, y;

int A[2][1001];

while (cin >> x >> y )

{

for (int i = 0; i < 2; i++){

for (int j = 0; j < 1001; j++){

A[i][j] = 0;

}

for (int i = 0; i < x.length(); i++){

for (int j = 0; j < y.length(); j++){

if (x[i] == y[j]) A[i % 2][(j + 1)] = 1 + A[(i + 1) % 2][j];

else A[i % 2][j + 1] = max(A[(i + 1) % 2][j + 1], A[i % 2][j]);

}

cout << A[(x.length() + 1) % 2][y.length()] << endl;

}

return 0;

}

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

Алгоритм поиска слова отдаленно напоминает таковой у алгоритма при поиске расстояния Левенштейна. В процессе сравнения буквы первого слова с буквами второго, нам понадобится информация о сравнениях предыдущей буквы слова. Для хранения этой информации создадим двумерный массив. Если буквы равны, увеличим уже полученную длину на один и передадим ее элементу массива, в котором будет храниться информация о сравнениях следующей буквы первого слова, в противном случае оценим максимальную возможную длину на данном этапе.

Задача

Строка символов называется палиндромом, если она одинаково читается в обоих направлениях, например, «madam», «bob».
Определите, сколько палиндромов заданной длины $K$ содержит заданная строка $S$.

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

В первой строке содержится целое число $K$ ($2 \leqslant K \leqslant 200$), а во второй – заданная строка $S$, состоящая только из латинских букв, причем большие и малые буквы различаются (т.е. «Bob» — не палиндром). Длина $S$ от $1$ до $30000$ символов.

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

В единственной строке должно находиться количество различных палиндромов длины $K$, содержащихся в $S$ (т.е. являющихся последовательностями подряд идущих символов в $S$) (различными считаются палиндромы, начинающиеся с разных позиций в $S$).

Тесты

Входные данные	Выходные данные
$3$	$3$
$babcbab$
$1$	$5$
$abcde$
$4$	$0$
$aarreeds$
$5$	$3$
$aaaaaaa$
$3$	$0$
$CaccaC$

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

String

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin >> k;
    string s;
    cin >> s;
    int l, r, flag=0, ans=0;
    for(int i=0; i<s.size()-k+1; i++)
    {
        flag=0;
        l=i;
        r=i+k-1;
        for(int j=0; j<k/2; j++)
        {
            if(s[l+j]!=s[r-j]){ 
                flag=1;
                break;
            }
        }
        if(flag==0){
            ans++;
        }
    }
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int k;

cin >> k;

string s;

cin >> s;

int l, r, flag=0, ans=0;

for(int i=0; i<s.size()-k+1; i++)

{

flag=0;

l=i;

r=i+k-1;

for(int j=0; j<k/2; j++)

{

if(s[l+j]!=s[r-j]){

flag=1;

break;

}

if(flag==0){

ans++;

}

cout << ans;

return 0;

}

C-String

#include <iostream>
#include <cstring>

using namespace std;

const int max_length=30001; 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin >> k;
    char s[max_length];
    cin >> s;
    int l, r, flag=0, ans=0;
    for(int i=0; i<strlen(s)-k+1; i++)
    {
        flag=0;
        l=i;
        r=i+k-1;
        for(int j=0; j<k/2; j++)
        {
            if(s[l+j]!=s[r-j]){ 
                flag=1;
                break;
            }
        }
        if(flag==0){
            ans++;
        }
    }
    cout << ans;
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

const int max_length=30001;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int k;

cin >> k;

char s[max_length];

cin >> s;

int l, r, flag=0, ans=0;

for(int i=0; i<strlen(s)-k+1; i++)

{

flag=0;

l=i;

r=i+k-1;

for(int j=0; j<k/2; j++)

{

if(s[l+j]!=s[r-j]){

flag=1;

break;

}

if(flag==0){

ans++;

}

cout << ans;

return 0;

}

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

Мы рассматриваем все подстроки строки $s$ длины $k$ и проверяем, является ли каждая подстрока палиндромом. В случае положительного ответа, увеличиваем счетчик. Проверка, является ли каждая подстрока палиндромом, выполняется следующим образом: мы ставим указатели на противоположные концы подстроки, далее сравниваем элементы на которые указывают указатели и если они равны, одновременно сдвигаем указатели на один к центру этой подстроки. Продолжаем этот процесс до тех пор, пока указатели не «встретятся». Если на каком то этапе элементы не равны, прекращаем процесс с отрицательным ответом для этой подстроки. Если же указатели «встретились», то эта подстрока является палиндромом.

Ссылки

Условие задачи на e-olymp
Код решения. String
Код решения. C-String

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

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

Tag Archives: подстроки

e-olymp 1079. Удаление букв

Задача

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

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

Тесты

String

C-String

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

Ссылки

Related Images:

e-olymp 670. Поиск палиндромов

Задача

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

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

Тесты

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

String

C-String

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

Ссылки

Related Images: