Задача взята с сайта e-olymp.com.
Условие задачи
По заданным двум строкам a и b следует вывести такую строку x наибольшей длины, которая одновременно является подстрокой перестановки a и подстрокой перестановки b.
Входные данные
Состоит из нескольких тестов, каждый их которых содержит две строки. То есть строки 1 и 2 — это первый тест, строки 3 и 4 — второй тест и т.д. Каждая строка состоит из символов нижнего регистра, причём первой строкой в паре является a, а второй строкой b. Максимальная длина каждой строки 1000 символов.
Выходные данные
Для каждого теста следует в отдельной строке вывести строку x. Если таких строк несколько, то вывести наименьшую в алфавитном порядке.
Тесты
| Входные данные | Выходные данные |
| walking down |
nw |
| the street |
et |
| abcd efg |
|
| abbcdd badbc |
abbcd |
Код программы
|
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 <string> using namespace std; int main() { string a, b; while(getline(cin, a) && getline(cin, b)){ for(char letter ='a'; letter <= 'z'; ){ if((a.find(letter)!=string::npos) && (b.find(letter)!=string::npos)){ /* если буква есть в обеих строках */ cout << letter; a.erase(a.find(letter),1); /* стираем найденную букву в первой строке */ b.erase(b.find(letter),1); /* стираем найденную букву во второй строке */ } else letter++; /* если буквы нет в обеих строках, переходим к следующей букве алфавита */ } cout << endl; } return 0; } |
Засчитанное решение на e-olymp.com.
Решение
Для решения данной задачи необходимо проходя по алфавиту, искать есть ли текущая буква в обеих строках и удалять её. Если буквы нет одновременно в обеих строках, необходимо перейти к следующей букве алфавита.
Хорошо. Зачтено.
Только поправьте отступ в 21-й строке.