Условия задачи

Два слова называются анаграмматически одинаковыми, если из букв одного слова можно получить другое слово. Например, occurs является анаграммой для слова succor; и наоборот, dear не является анаграммой слова dared (так как буква d встречается дважды в dared, и только один раз в dear). Наиболее известной английской анаграммой являются слова dog и god.

Анаграмматическим расстоянием двух слов называется минимальное количество букв, которые нужно удалить, чтобы в результате два слова стали анаграмматически одинаковыми. Например, для слов sleep и leap, нужно удалить как минимум три буквы — две из sleep и одну из leap — чтобы остались анаграмматически одинаковые слова (в указанном случае lep). А для слов dog и cat, в которых нет одинаковых букв, анаграмматическое расстояние равно [latex]6[/latex], так как нужно удалить все буквы (любое слово, в том числе и пустая строка, являются анаграммой само к себе).

Ваша задача найти анаграмматическое расстояние для заданных двух слов.

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

В первой строке задано положительное целое число [latex]N[/latex] (не превышающее [latex]60000[/latex]), указывающее количество тестовых примеров. Каждый тестовый пример состоит из двух слов, возможно пустых, каждое из которых записано в отдельной строке (всего [latex]2N[/latex]последующих строк).

Все слова, имеющие не нулевую длину, сформированы из строчных букв английского алфавита (abcdefghijklmnopqrstuvwxyz). Самым длинным словом является pneumonoultramicroscopicsilicovolcanoconiosis.

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

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

Ссылка на задачу находится здесь.

Тесты

№	Входные данные	Выходные данные
1	4 crocus succor dares seared empty smell lemon	Case #1: 0 Case #2: 1 Case #3: 5 Case #4: 4
2	1	Case #1: 0
3	5 lol lolipop primate mathematics kangaroo kilimanjaro sister sisters android andromeda	Case #1: 4 Case #2: 8 Case #3: 7 Case #4: 1 Case #5: 4

Код (cstring)

#include <cstring>
#include <iostream>
using namespace std;

const short maxSize = 46;

int main() {
	int n, matchingLetters;
	cin >> n;
	cin.ignore();
	char *word_1 = new char[maxSize]; 
	char *word_2 = new char[maxSize];
	for (int i = 0; i < n; i++) {
		 matchingLetters = 0;
		 cin.getline(word_1, maxSize);
		 cin.getline(word_2, maxSize);
		 for (int j = 0; j < strlen(word_1); j++) {
		 	  for (int k = 0; k < strlen(word_2); k++)  {
		 	  	   if (word_1[j] == word_2[k]) {
		 	  	   	   word_2[k] = '#';
		 	  	       matchingLetters++;
		 	  	       break;
		 	  	   }
		 	  }
		 }
		 cout << "Case #" << i + 1 << ":  " << strlen(word_1) + strlen(word_2) - 2 * matchingLetters << endl;
	}
	return 0;
}

#include <cstring>

#include <iostream>

using namespace std;

const short maxSize = 46;

int main() {

int n, matchingLetters;

cin >> n;

cin.ignore();

char *word_1 = new char[maxSize];

char *word_2 = new char[maxSize];

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

matchingLetters = 0;

cin.getline(word_1, maxSize);

cin.getline(word_2, maxSize);

for (int j = 0; j < strlen(word_1); j++) {

for (int k = 0; k < strlen(word_2); k++) {

if (word_1[j] == word_2[k]) {

word_2[k] = '#';

matchingLetters++;

break;

}

cout << "Case #" << i + 1 << ": " << strlen(word_1) + strlen(word_2) - 2 * matchingLetters << endl;

}

return 0;

}

Код на ideone можно найти здесь.

Ход решения

Наша задача состоит в определении количества символов в двух строках, которые необходимо удалить для того, чтобы слова считались анаграммами. Используем после ввода числа примеров [latex]n[/latex] функцию cin.ignore(), для игнорирования перехода на новую строку, а затем считываем по парам слова. Последовательно проходим все буквы слова в первой строке с помощью цикла for. Если находим эту букву в слове второй строки, увеличиваем счётчик совпадающих букв. Совпадающую букву во второй строке заменяем на символ #, дабы избежать повторных проверок одной и той же буквы в случае её неоднократного появления в первой строке. Общее количество букв в двух строках равняется сумме длин первой и второй строк. Таким образом, чтобы получить анаграмматическое расстояние необходимо вывести:

strlen(word_1) + strlen(word_2) - 2 * matchingLetters

26	strlen(word_1) + strlen(word_2) - 2 * matchingLetters

Умножение matchingLetters на [latex]2[/latex] возникает вследствие того, что (по факту) нужно зачёркивать символы в двух строках.

Стоит отметить, что в задаче не требуется реализовывать поиск символа самостоятельно. Можно воспользоваться уже встроенной функцией для работы со строками strchr(), которая вернёт нам указатель на искомый символ. Если символ не будет найден, функция вернёт NULL. Тогда наш код приобретает следующий вид:

#include <cstring>
#include <iostream>
using namespace std;

const short maxSize = 46;

int main() {
	int n, matchingLetters;
	cin >> n;
	cin.ignore();
	char *word_1 = new char[maxSize]; 
	char *word_2 = new char[maxSize];
	for (int i = 0; i < n; i++) {
		 matchingLetters = 0;
		 cin.getline(word_1, maxSize);
		 cin.getline(word_2, maxSize);
		 for (int j = 0; j < strlen(word_1); j++) {
		 	  if (strchr(word_2, word_1[j])) {
		 	  	   *strchr(word_2, word_1[j]) = '#';
		 	  	   matchingLetters++;
		 	  }
		 }
		 cout << "Case #" << i + 1 << ":  " << strlen(word_1) + strlen(word_2) - 2 * matchingLetters << endl;
	}
	return 0;
}

#include <cstring>

#include <iostream>

using namespace std;

const short maxSize = 46;

int main() {

int n, matchingLetters;

cin >> n;

cin.ignore();

char *word_1 = new char[maxSize];

char *word_2 = new char[maxSize];

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

matchingLetters = 0;

cin.getline(word_1, maxSize);

cin.getline(word_2, maxSize);

for (int j = 0; j < strlen(word_1); j++) {

if (strchr(word_2, word_1[j])) {

*strchr(word_2, word_1[j]) = '#';

matchingLetters++;

}

cout << "Case #" << i + 1 << ": " << strlen(word_1) + strlen(word_2) - 2 * matchingLetters << endl;

}

return 0;

}

Код на ideone можно найти здесь.

Код (string)

#include <string>
#include <iostream>
using namespace std;

int main() {
	int n, matchingLetters;
	cin >> n;
	cin.ignore();
	string word_1, word_2;
	for (int i = 0; i < n; i++) {
		 matchingLetters = 0;
		 getline(cin, word_1);
		 getline(cin, word_2);
		 for (int j = 0; j < word_1.size(); j++) {
		 	  if (word_2.find(word_1[j]) != string::npos) {
		 	  	  word_2[word_2.find(word_1[j])] = '#';
		 	  	  matchingLetters++;
		 	  }
		 }
		 cout << "Case #" << i + 1 << ":  " << word_1.size() + word_2.size() - 2 * matchingLetters << endl;
	}
	return 0;
}

#include <string>

#include <iostream>

using namespace std;

int main() {

int n, matchingLetters;

cin >> n;

cin.ignore();

string word_1, word_2;

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

matchingLetters = 0;

getline(cin, word_1);

getline(cin, word_2);

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

if (word_2.find(word_1[j]) != string::npos) {

word_2[word_2.find(word_1[j])] = '#';

matchingLetters++;

}

cout << "Case #" << i + 1 << ": " << word_1.size() + word_2.size() - 2 * matchingLetters << endl;

}

return 0;

}

В случае решения данной задачи с помощью класса string используем функцию find() для поиска заданного символа в строке.

Код на ideone можно найти здесь.

Ссылка на засчитанное решение.

Related Images:

Задача. Палиндром

Условие задачи

Палиндром — это строка, которая одинаково читается слева направо и справа налево. Составьте программу, которая проверяет, является ли заданный текст палиндромом. Не забудьте, что при чтении пробел никак не произносится.

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

Дана строка [latex]S[/latex], [latex]|S| \leq 255[/latex], состоящая из строчных латинских букв и пробелов. Под [latex]|S|[/latex] подразумевается длина строки.

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

Требуется вывести «YES«, если текст является палиндромом, «NO» если не является.

Также условие задачи можно посмотреть здесь.

Тестирование

№	Входные данные	Выходные данные
1.	palindrom	NO
2.	a roza upala na lapu azora	YES
3.	my gym	YES
4.	character	NO

Реализация (с использованием c-string)

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
	const int startSize = 256;
	char s[startSize];
	char s_1[startSize];
	cin.getline(s, 256);
	int j = 0;
	for (int i = 0; i < startSize; i++)
	{
		if (s[i] == ' ') continue; 
		//учитываем, что пробел при чтении никак не произносится
		s_1[j] = s[i];
		j++;
	}
	int resSize = strlen(s_1);
	char * s_2 = new char[resSize + 1];
	for (int i = 0; i < resSize; i++)
	{
		s_2[i] = s_1[resSize - 1 - i];
	}
	s_2[resSize] = '\0';
	if (!strcmp(s_1, s_2))
	{
		cout << "YES\n";
	}
	else
	{
		cout << "NO\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int main()

{

const int startSize = 256;

char s[startSize];

char s_1[startSize];

cin.getline(s, 256);

int j = 0;

for (int i = 0; i < startSize; i++)

{

if (s[i] == ' ') continue;

//учитываем, что пробел при чтении никак не произносится

s_1[j] = s[i];

j++;

}

int resSize = strlen(s_1);

char * s_2 = new char[resSize + 1];

for (int i = 0; i < resSize; i++)

{

s_2[i] = s_1[resSize - 1 - i];

}

s_2[resSize] = '\0';

if (!strcmp(s_1, s_2))

{

cout << "YES\n";

}

else

{

cout << "NO\n";

}

return 0;

}

Алгоритм решения (c-string)

С помощью функции [latex]strcmp()[/latex] сравниваем символы строк [latex] s_1[/latex] и [latex]s_2[/latex], предварительно учтя тот факт, что пробел при чтении никак не произносится. Если они идентичны, введенный текст одинаково читается слева направо и справа налево, то есть является палиндромом. В противном случае, текст палиндромом не является. Важно отметить, что функция [latex]strcmp()[/latex] учитывает регистр введенных символов, согласно условию мы должны использовать строчные латинские буквы.

Для запроса на выполнение следует перейти по ссылке.

Ссылка на засчитанное решение на e-olymp.com.

Реализация (с использованием string)

#include <iostream>
#include <string>
using namespace std;
 
int main() {
	string s;
    char c;
    while (cin >> c)
    {
        if (c != ' ') 
        	s.push_back(c);
    }
    if (s.empty())
    {
        cout << "YES";
        return 0;
    }
    bool palindrom = true;
    for (int i = 0; i <= s.length()/2; i++)
    {
        if (s.at(i) != s.at(s.length()-1-i))
        {
            palindrom = false;
            break;
        }
    }
    cout << (palindrom ? "YES" : "NO");
	return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

char c;

while (cin >> c)

{

if (c != ' ')

s.push_back(c);

}

if (s.empty())

{

cout << "YES";

return 0;

}

bool palindrom = true;

for (int i = 0; i <= s.length()/2; i++)

{

if (s.at(i) != s.at(s.length()-1-i))

{

palindrom = false;

break;

}

cout << (palindrom ? "YES" : "NO");

return 0;

}

Алгоритм решения (string)

Сравниваем соответствующие символы строки до середины, проверяя тем самым, читается ли введенный текст одинаково справа налево и слева направо, то есть является палиндромом. Учитываем, что пробел при чтении никак не произносится: считываем из входного потока по символу и помещаем в строку только буквы.

Для запроса на выполнение следует перейти по ссылке.

Ссылка на засчитанное решение на e-olymp.com.

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

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

Tag Archives: работа со строками

e-olymp 1080. Анаграмматическое расстояние

Related Images:

e-olymp 2162. Палиндром

Задача. Палиндром

Условие задачи

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

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

Тестирование

Реализация (с использованием c-string)

Алгоритм решения (c-string)

Реализация (с использованием string)

Алгоритм решения (string)

Related Images: