Задача
Вам задано два слова, каждое из которых состоит из заглавных английских букв. Удалите из них несколько букв так, чтобы в результате получились одинаковые слова.
Найдите максимально возможную длину полученного слова.
Входные данные
Каждый тест состоит из одной строки, содержащей два заданных слова, разделенных пробелом. Длина каждого слова от $1$ до $200$ символов. Всего имеется не более $10$ тестов.
Выходные данные
Для каждого теста выведите максимально возможную длину полученных одинаковых слов (длину максимального слова, которое можно получить путем удаления некоторых букв). Если одинаковые слова получить невозможно, то выведите $0$.
Тесты
Входные данные | Выходные данные |
---|---|
AAABBB ABABAB AXYAAZ CCCXCCCYCCCZCC |
4 3 |
AAAAA BBBBB | 0 |
ABABA BCACB | 3 |
STRING GNIRTS | 1 |
String
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#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; } |
Решение задачи
Алгоритм поиска слова отдаленно напоминает таковой у алгоритма при поиске расстояния Левенштейна. В процессе сравнения буквы первого слова с буквами второго, нам понадобится информация о сравнениях предыдущей буквы слова. Для хранения этой информации создадим двумерный массив. Если буквы равны, увеличим уже полученную длину на один и передадим ее элементу массива, в котором будет храниться информация о сравнениях следующей буквы первого слова, в противном случае оценим максимальную возможную длину на данном этапе.
Ссылки
Условие задачи на сайте E-Olymp
код задачи (string) на Ideone
код задачи (c-string) на Ideone
описание расстояния Левенштейна на Wikipedia
One thought on “e-olymp 1079. Удаление букв”