Анаграммы

26/11/2018 by Иван Киреев

Анаграммы

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

После того как он закончил выписывать все перестановки Игорь устал и пошел учиться. Он взял словарь и начал учить новые слова. Через некоторое время Игорь заметил что некоторые из слов в словаре совпадают с записанными им перестановками на листке и задался вопросом, — а какие можно получить слова переставляя буквы из других в словаре.

Игоря будут интересовать только слова которые записаны в словаре, так как других он не знает.

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

Его программа работала слишком долго, поэтому он попросил вас написать новую которая справилась бы с этой задачей.

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

Задан словарь английских слов. Каждое слово в новой строке. Длинна слова не более $255$ символов. Количество слов любое.

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

Вывести все слова что имеют максимальное количество анаграмм в нем.

Решение

Прочитаем словарь. Запишем в структуру pair строку с исходным словом в first и отсортированную в second. Анаграммами будут являться слова с одинаковыми second строками. Так как они будут состоять из одних и тех же букв, которые выстроены в одинаковом порядке. Отсортируем множество слов из словаря по second. Таким образом все слова анаграммы будут находиться рядом.

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

На выходе получим массив индексов слов у которых существует максимальное количество анаграмм, в данном словаре. Выведем эти слова и все анаграммы к ним в исходном варианте. Для этого нам и нужна строка first.

Тесты

№

Ввод

Вывод

2500 слов английского языка

trace react crate

dear dare read

post stop spot

Код

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#define DIFFERENCE ('A' - 'a') // разность регистров
using namespace std;
bool IsBigAlpha(char a) {
	return (a >= 'A' && a <= 'Z');
}
bool IsSmalAlpha(char a) {
	return (a >= 'a' && a <= 'z');
}
string edit(const string &str) { // приводим всё к нижнему регистру и  убираем лишние символы
	string rez = "";
	for(char a : str) {
		if (IsBigAlpha(a)) a -= DIFERENSE;
		if (IsSmalAlpha(a)) rez += a;
	}
	return rez;
}
bool comp(const pair<string, string> &a, const pair<string, string> &b) { // сравнитель по второй строке
	return a.second < b.second;
}
int main() {
	vector <pair<string, string>> words; // словарь
	string str;
	while (getline(cin, str, '\n')) {
		pair<string, string> word; // слово
		word.first = str;
		word.second = edit(str);
		sort(word.second.begin(), word.second.end()); // сортируем буквы в слове
		words.push_back(word);
	}
	sort(words.begin(), words.end(), comp); // сортируем словарь по анаграммам
	vector <int> indeces; // массив индексов
	int Count = 0, MaxCount = 0, n = words.size();
	for (int i = 1; i < n; i++) {
		if (words[i-1].second == words[i].second) Count++; 
		else {
			if (Count > MaxCount) { 
				MaxCount = Count;
				indeces.clear();
				indeces.push_back(i-1);
			} else if (Count == MaxCount) indeces.push_back(i-1);
			Count = 0;
		}
	}
	if (Count > MaxCount) {  // обрабатываем последний найденный набор анаграмм
				MaxCount = Count;
				indeces.clear();
				indeces.push_back(n-1);
	} else if (Count == MaxCount) indeces.push_back(n-1);
	bool first = 1;
	for (int index : indeces) { // выводим
		if (!first) cout << endl << "---------------" << endl;
		else first = 0;
		for (int i = 0; i <= MaxCount; i++) {
			if (i != 0) cout << endl;
			cout << words[index - i].first;
		}
	}
	return 0;
}

#include <iostream>

#include <string>

#include <algorithm>

#include <vector>

#define DIFFERENCE ('A' - 'a') // разность регистров

using namespace std;

bool IsBigAlpha(char a) {

return (a >= 'A' && a <= 'Z');

}

bool IsSmalAlpha(char a) {

return (a >= 'a' && a <= 'z');

}

string edit(const string &str) { // приводим всё к нижнему регистру и убираем лишние символы

string rez = "";

for(char a : str) {

if (IsBigAlpha(a)) a -= DIFERENSE;

if (IsSmalAlpha(a)) rez += a;

}

return rez;

}

bool comp(const pair<string, string> &a, const pair<string, string> &b) { // сравнитель по второй строке

return a.second < b.second;

}

int main() {

vector <pair<string, string>> words; // словарь

string str;

while (getline(cin, str, '\n')) {

pair<string, string> word; // слово

word.first = str;

word.second = edit(str);

sort(word.second.begin(), word.second.end()); // сортируем буквы в слове

words.push_back(word);

}

sort(words.begin(), words.end(), comp); // сортируем словарь по анаграммам

vector <int> indeces; // массив индексов

int Count = 0, MaxCount = 0, n = words.size();

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

if (words[i-1].second == words[i].second) Count++;

else {

if (Count > MaxCount) {

MaxCount = Count;

indeces.clear();

indeces.push_back(i-1);

} else if (Count == MaxCount) indeces.push_back(i-1);

Count = 0;

}

if (Count > MaxCount) { // обрабатываем последний найденный набор анаграмм

MaxCount = Count;

indeces.clear();

indeces.push_back(n-1);

} else if (Count == MaxCount) indeces.push_back(n-1);

bool first = 1;

for (int index : indeces) { // выводим

if (!first) cout << endl << "---------------" << endl;

else first = 0;

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

if (i != 0) cout << endl;

cout << words[index - i].first;

}

return 0;

}

Код на ideone

Related Images:

Ю12.34

20/12/2014 by Недомовний Владислав

Задача.

«Балда». Для заданного достаточно длинного слова найти в имеющемся словаре все слова, в которых использованы только буквы, имеющиеся в заданном слове (с учетом кратности вхождения).

Тесты.

Ввод	Вывод	Комментарий
programming	a in on go no an man am or arm air ring ago pain grin rain mom main among roar grip pair rip map nor aim iron program pin ma moan groan gang gain rag pig piano ramp gin ram rig	Пройден
polymorphism	is his him my so or room sir ship lip slip mom shop simply pop rip poor pool sip oil holy hip limp hop prop spy loom	Пройден

В качестве словаря используется список 2500 наиболее употребительных английских слов (составлен Александром Васильевым).

Код(string).

#include <iostream>
using namespace std;

int main() {
	string word; //описание строк для хранения исходного слова и слов из словаря
	cin >> word;
	string dict;
	bool b1,b2; //описание вспомогательных переменных
	string temp;
	while (cin >> dict)
	{
		temp=word;
		b1=true; 
		for (size_t j=0;j<dict.length();j++) // проверяем или все символы из dict содержатся в temp
		{
			b2=false;
			for (size_t i=0;i<temp.length();i++)
			{
				if(dict[j]==temp[i])
				{
					b2=true;
					temp[i]='.';
					break;
				}
			}
			if (!b2)
			{
				b1=false;
				break;
			}
		}
		if (b1) cout << dict << " ";
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

string word; //описание строк для хранения исходного слова и слов из словаря

cin >> word;

string dict;

bool b1,b2; //описание вспомогательных переменных

string temp;

while (cin >> dict)

{

temp=word;

b1=true;

for (size_t j=0;j<dict.length();j++) // проверяем или все символы из dict содержатся в temp

{

b2=false;

for (size_t i=0;i<temp.length();i++)

{

if(dict[j]==temp[i])

{

b2=true;

temp[i]='.';

break;

}

if (!b2)

{

b1=false;

break;

}

if (b1) cout << dict << " ";

}

return 0;

}

Используем ввод как условие цикла while. Вводим вспомогательную строку temp, в которую записываем исходное слово. Символы строки temp, которые совпадают с символами данного слова из словаря, заменяем на точки (подходят любые символы, кроме английских букв), учитывая, таким образом, кратность вхождения. Также для проверки вводим логические переменные b1(содержатся ли все символы из строки dict в temp?) и b2(содержится ли j-ый символ из dict в temp?).

Данный код на ideone.

Код(c-string).

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

int main() {
	char word[100]; //описание символьных массивов для хранения исходного слова и слов из словаря
	cin >> word;
	char dict[100];
	bool b1,b2; //описание вспомогательных переменных
	char temp[strlen(word)];
	for (size_t i=0;word[i]!='';i++)
	{
		temp[i]=word[i];
	}
	while (cin >> dict)
	{
		strcpy(temp,word);
		b1=true;
		for (size_t j=0;dict[j]!='';j++) // проверяем или все символы из dict содержатся в temp
		{
			b2=false;
			for (size_t i=0;temp[i]!='';i++)
			{
				if(dict[j]==temp[i])
				{
					b2=true;
					temp[i]='.';
					break;
				}
			}
			if (!b2)
			{
				b1=false;
				break;
			}
		}
		if (b1) cout << dict << " ";
	}
	return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char word[100]; //описание символьных массивов для хранения исходного слова и слов из словаря

cin >> word;

char dict[100];

bool b1,b2; //описание вспомогательных переменных

char temp[strlen(word)];

for (size_t i=0;word[i]!='';i++)

{

temp[i]=word[i];

}

while (cin >> dict)

{

strcpy(temp,word);

b1=true;

for (size_t j=0;dict[j]!='';j++) // проверяем или все символы из dict содержатся в temp

{

b2=false;

for (size_t i=0;temp[i]!='';i++)

{

if(dict[j]==temp[i])

{

b2=true;

temp[i]='.';

break;

}

if (!b2)

{

b1=false;

break;

}

if (b1) cout << dict << " ";

}

return 0;

}

Решение аналогично.

Данный код на ideone.

Related Images:

Ю12.36

27/11/2014 by Оніщенко Олександр

Задача: Разнобуквица. Из имеющегося словаря выбрать наиболее длинное слово, в котором все буквы разные, например: ЛЕЙКОПЛАСТЫРЬ, НЕРЯШЛИВОСТЬ, ЧЕТЫРЁХДЮЙМОВКА.

Тесты:

Словарь	Результат	Комментарий
There, here, the, then	then	Пройден
Список 2500 наиболее употребительных английских слов	background	Пройден

Код:

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

int main() {
	string s, max;  // Оригинал, копия, самое длинное слово   
	int n = 0;         //Счетчик размерности слова
	while (cin >> s) {                                 
		while(!isalpha(s[0])) s.erase(0,1);               // Строка не будет 
		while(!isalpha(s[s.length()-1])) s.pop_back();   // просматривать знаки препинания и т.п. 
		bool x = 1;                                //Создаем булеву переменную
		for (int i = 0; i < s.length(); i++)      	//Создаем 2 цикла для проверки на повторение  
			for (int j = i+1; j < s.length(); j++)//каждой буквы в слове.
				if (s[i] == s[j]) {    //Если одна из букв встречается больше одного раза   
					x = 0;            //в одном слове, присваиваем х значение "false" и
					break;           // прерываем цикл проверки.
				}
		if(x && s.length() > n) {   //Если же значение х "true", то присваиваем максимально 
			n = s.length();        // длинное слово max.
			max = s;
		}
	}
	cout << max;          //Выводим результат.
	return 0;
 }

#include <iostream>

#include <string>

using namespace std;

int main() {

string s, max; // Оригинал, копия, самое длинное слово

int n = 0; //Счетчик размерности слова

while (cin >> s) {

while(!isalpha(s[0])) s.erase(0,1); // Строка не будет

while(!isalpha(s[s.length()-1])) s.pop_back(); // просматривать знаки препинания и т.п.

bool x = 1; //Создаем булеву переменную

for (int i = 0; i < s.length(); i++) //Создаем 2 цикла для проверки на повторение

for (int j = i+1; j < s.length(); j++)//каждой буквы в слове.

if (s[i] == s[j]) { //Если одна из букв встречается больше одного раза

x = 0; //в одном слове, присваиваем х значение "false" и

break; // прерываем цикл проверки.

}

if(x && s.length() > n) { //Если же значение х "true", то присваиваем максимально

n = s.length(); // длинное слово max.

max = s;

}

cout << max; //Выводим результат.

return 0;

}

Для того что бы найти искомое слово создаем две строки, одна для ввода словаря, другая для результата. Создаем цикл [latex]while[/latex] . С помощью функции [latex]isalpha()[/latex] отсеиваем знаки препинания в словаре. Далее создаем булеву переменную [latex]x[/latex] и два цикла [latex]for[/latex] что бы проверить встречается ли буква в слове больше одного раза, если хоть одна буква повторяется, то присваиваем [latex]x[/latex] значение «false» и прерываем цикл [latex]for[/latex]. Если значение булевой переменной «true», значит в слове нет повторяющихся букв, из таких слов теперь можно искать самое длинное, для этого счетчику [latex]n[/latex] присваиваем размерность самого длинного слово, и присваиваем его значение в строку [latex]max[/latex]. Выводим результат.

Ссылка Ideone.

Related Images:

Ю12.19

24/11/2014 by Марченко Філіп Олександрович

Задача: В имеющемся словаре найти группы слов, записанных одними и теми же буквами и отличающиеся только их порядком, то есть перестановкой, например, (КОРМА, КОМАР).

Код:

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>

using namespace std;
int count_words (string s) //функция подсчитывает слова в строке
{
    s+=' ';
    int a = 0;
    for (size_t i=0; i<s.length(); i++)
        if (s[i]==' ') a++;
    return a;
}
string * cut_words (string s) //функция разрезает строку на слова и возвращает массив
{
    s+=' ';
    int c = 0;
    int p = 0;
    int i=0;
    string *s_return = new string [count_words(s)];
    while (s.length() != 0)
        {
            if (s[i] != ' ')
            {
                c++;
                i++;
            }
            else
            {
                i=0;
                s_return[p] = s.substr(0, c);
                s.erase(0, c+1);
                c = 0;
                p++;
            }
        }
   return s_return;
}

int main ()
{
    string s;
    getline (cin, s);
	string *s_return;
	s_return = cut_words(s);
	for (int i=0; i<count_words(s); i++)
    {
    	string s_tmp = s_return[i];
        if (s_tmp.empty())					//если ячейка пуста, то продолжаем дальше
            {
                continue;
            }
        else				//а если нет, то ищем перестановки.
        {
        	int p = 0;
            for (int j=i+1; j<count_words(s); j++)
            {
                if ( is_permutation (s_tmp.begin(), s_tmp.end(), s_return[j].begin()))	//если перестановка
                    if (s_tmp.length() == s_return[j].length())		//и если одинаковая длина слов
                    {
                        cout<<s_return[j]<<endl;		//выводим на экран
                        s_return[j].clear(); //очищаем строку
                        p++;
                    }
            }
            if (p>=1) cout<<s_tmp<<endl;	
        }
    }
    return 0;
}

#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <string>

using namespace std;

int count_words (string s) //функция подсчитывает слова в строке

{

s+=' ';

int a = 0;

for (size_t i=0; i<s.length(); i++)

if (s[i]==' ') a++;

return a;

}

string * cut_words (string s) //функция разрезает строку на слова и возвращает массив

{

s+=' ';

int c = 0;

int p = 0;

int i=0;

string *s_return = new string [count_words(s)];

while (s.length() != 0)

{

if (s[i] != ' ')

{

c++;

i++;

}

else

{

i=0;

s_return[p] = s.substr(0, c);

s.erase(0, c+1);

c = 0;

p++;

}

return s_return;

}

int main ()

{

string s;

getline (cin, s);

string *s_return;

s_return = cut_words(s);

for (int i=0; i<count_words(s); i++)

{

string s_tmp = s_return[i];

if (s_tmp.empty()) //если ячейка пуста, то продолжаем дальше

{

continue;

}

else //а если нет, то ищем перестановки.

{

int p = 0;

for (int j=i+1; j<count_words(s); j++)

{

if ( is_permutation (s_tmp.begin(), s_tmp.end(), s_return[j].begin())) //если перестановка

if (s_tmp.length() == s_return[j].length()) //и если одинаковая длина слов

{

cout<<s_return[j]<<endl; //выводим на экран

s_return[j].clear(); //очищаем строку

p++;

}

if (p>=1) cout<<s_tmp<<endl;

}

return 0;

}

Тесты:

Исходный словарь	Обработанный словарь
the and a to I is of have you he it in not was that his do on with she at say her for as are we but can him they up what out me go get this from be look my there know all one no see will back into like if were then an come think so down your them would about man take just by am now over make been or time when hand who want here tell off right their turn two through eye head other how some more around door room face day where way night well thing open away give only something ask move stand good find again little try too still hear walk before leave sit let long call feel close very why which car any hold work run never start even light than after put yes stop old watch first may talk another cut mean pull behind smile our toward towards much its house keep place begin nothing year woman side because three seem wait need moment himself stare arm use voice last late across sure front sound big really name should new anything against guy kill point small happen wall black step window life maybe fall own far under boy	no on three there own now how who thing night its sit name mean
Все слова

Алгоритм:

Для решения данной задачи я воспользовался возможностью, которую мне предоставляет библиотека <algorithm> . Поскольку мне надо было проверить, являются ли строки перестановками строки s_tmp, которую я ставлю в роли исходной с каждой итерацией, я воспользовался функцией is_permutation . Если некая строка является перестановкой, то она выводится на экран и стирается. С последующими итерациями будет проводится проверка на наличие на том или ином месте строки. Если строки обнаружено не будет, программа перейдёт к следующей итерации.

Для проверки правильности работы программы, воспользуйтесь ссылкой .

UPD: Поскольку я понял, что вводить вначале количество слов неудобно, я решил написать функцию, которая сама создаст массив из введённой мной строкой.