2040. Обычная перестановка

По заданным двум строкам a и b следует вывести такую строку x наибольшей длины, которая одновременно является подстрокой перестановки a и подстрокой перестановки b.

Вход. Состоит из нескольких тестов, каждый их которых содержит две строки. Каждая строка состоит из символов нижнего регистра, причём первой строкой в паре является a, а второй строкой b. Максимальная длина каждой строки 1000 символов.

Выход. Для каждого теста выведите строку x. Если таких строк несколько, то выведите наименьшую в алфавитном порядке.

Пример входа	Пример выхода
pretty women walking down the street	e nw et

РЕШЕНИЕ

структуры данных - map

Анализ алгоритма

Подсчитаем количество каждой буквы, которая встречается в a и b. Находим, сколько и каких букв одновременно принадлежит строкам a и b. Выводим их (с учетом количества) в алфавитном порядке.

Реализация алгоритма

Входные строки считываем в массивы a и b. В отображениях aa и bb будем подсчитывать, сколько и каких букв содержится в a и b.

char a[1010], b[1010];

map<char,int> aa, bb;

Для каждого теста читаем входные строки a и b. Заполняем отображения aa и bb.

while(gets(a))

{

gets(b);

aa.clear(); bb.clear();

for(i = 0; i < strlen(a); i++) aa[a[i]]++;

for(i = 0; i < strlen(b); i++) bb[b[i]]++;

Выводим общие буквы строк a и b в алфавитном порядке. При этом каждую букву выводим столько раз, сколько она встречается одновременно в a и b.

for(i = 'a'; i <= 'z'; i++)

{

m = min(aa[i],bb[i]);

for(j = 0; j < m; j++) printf("%c",i);

}

printf("\n");

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

while(con.hasNext())

{

String a = con.nextLine();

String b = con.nextLine();

int aa[] = new int[256];

int bb[] = new int[256];

for(int i = 0; i < a.length(); i++) aa[a.charAt(i)]++;

for(int i = 0; i < b.length(); i++) bb[b.charAt(i)]++;

for(int i = 'a'; i <= 'z'; i++)

{

int m = Math.min(aa[i],bb[i]);

for(int j = 0; j < m; j++) System.out.print((char)i);

}

System.out.println();

}

}

}