Ю12.19

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

Код:

#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: Поскольку я понял, что вводить вначале количество слов неудобно, я решил написать функцию, которая сама создаст массив из введённой мной строкой.

Related Images:

Похожее

3 thoughts on “Ю12.19”

— Посмотрите, пожалуйста, здесь почти в конце перед видеолекциями должен быть словарь английских слов.
— И сюда нужно заглянуть.
— clear() не очищает память. Длине строки присваивается значение 0, но capacity не изменяется и все символы строки остаются в памяти.
— Пожалуйста, печатайте только те группы слов, где их больше одного. Каждую группу с новой строки.

Марченко Філіп Олександрович says: 27/11/2014 at 23:11

Исправлено. C-string выложу позже.
Насчёт теста «Все слова»: работало долго, дымясь, пыхтя и проклиная меня, но выдало ответ.

— Добавьте в метки слово «анаграмма».
— В 62-й строке лучше пробел, чем новая строка. Анаграммы будут в отдельной строке.
— Ещё один небольшой недочёт — если встречаются одинаковые слова их не стоит считать анаграммой.
— Основная проблема. Программа не успевает за 15 секунд отработать словарь из ~2500 слов. Это нереально долго. Для проверки я написал простой код с квадратичной сложностью по числу слов. Он успевает. Используйте его для тестирования если нужно. Но программа должна успеть обработать все данные из тестового словаря.

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

int main() {
	vector<string> voc;	// словарь (можно использовать массив с запасом)
	string word; 		// очередное слово
	while (cin >> word) voc.push_back(word); // читаем и запоминаем слово
	for (auto i = voc.begin(); i != voc.end(); i++){
		bool found = false; // предполагаем, что у слова нет анаграммы
		for (auto j = i + 1; j != voc.end();) {
			if (i->length() == j->length() && *i != *j &&	// анаграмма?
				is_permutation(i->begin(), i->end(), j->begin())) {
					cout << *j << " ";	// печатаем то, что нашли
					voc.erase(j);		// удаляем то, что нашли
					found = true;		// отмечаем, что у слова есть анаграмма
				} else j++;				// проверяем следующее слово
		}
		if (found) cout << *i << endl; // печатаем если есть анаграммы
	}
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

vector<string> voc; // словарь (можно использовать массив с запасом)

string word; // очередное слово

while (cin >> word) voc.push_back(word); // читаем и запоминаем слово

for (auto i = voc.begin(); i != voc.end(); i++){

bool found = false; // предполагаем, что у слова нет анаграммы

for (auto j = i + 1; j != voc.end();) {

if (i->length() == j->length() && *i != *j && // анаграмма?

is_permutation(i->begin(), i->end(), j->begin())) {

cout << *j << " "; // печатаем то, что нашли

voc.erase(j); // удаляем то, что нашли

found = true; // отмечаем, что у слова есть анаграмма

} else j++; // проверяем следующее слово

}

if (found) cout << *i << endl; // печатаем если есть анаграммы

}

Выполнить
Существенно ускорить (до n*log(n)) можно при помощи специальной сортировки. Нужно составить алгоритм компаратора, который сравнивает строки по числу использованных букв. Самый простой способ сделать это — отсортировать буквы в словах. После сортировки по отсортированным словам (забавно звучит!), все анаграммы окажутся рядом. Это добавит несколько строк кода, но программа будет существенно быстрее:

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

bool less_than(string x, string y) {
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	return x < y;
}

bool is_anagram(string x, string y) {
	if (x != y) {
		sort(x.begin(), x.end());
		sort(y.begin(), y.end());
		return x == y;
	}
	return false;
}

int main() {
	vector<string> voc;	// словарь (можно использовать массив с запасом)
	string word; 		// очередное слово
	while (cin >> word) voc.push_back(word); // читаем и запоминаем слово
	sort(voc.begin(), voc.end(), less_than); // по использованию букв
	bool found = false;
	cout << "Anagrams list:";
	for (auto i = voc.begin(); i != voc.end() - 1; i++) {
		if (is_anagram(*i, *(i + 1))) {
			if (!found) cout << endl << *i << " ";
			cout << *(i + 1) << " ";
			found = true;
		} else found = false;
	}
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

bool less_than(string x, string y) {

sort(x.begin(), x.end());

sort(y.begin(), y.end());

return x < y;

}

bool is_anagram(string x, string y) {

if (x != y) {

sort(x.begin(), x.end());

sort(y.begin(), y.end());

return x == y;

}

return false;

}

int main() {

vector<string> voc; // словарь (можно использовать массив с запасом)

string word; // очередное слово

while (cin >> word) voc.push_back(word); // читаем и запоминаем слово

sort(voc.begin(), voc.end(), less_than); // по использованию букв

bool found = false;

cout << "Anagrams list:";

for (auto i = voc.begin(); i != voc.end() - 1; i++) {

if (is_anagram(*i, *(i + 1))) {

if (!found) cout << endl << *i << " ";

cout << *(i + 1) << " ";

found = true;

} else found = false;

}

Выполнить
Дальнейшее сокращение времени работы программы потребует дополнительной памяти для хранения сортированных побуквенно слов в виде ключей к обычным словам (т.е. структур вида key=>value).