Developing.ru

Ребят, помогите пожалуйста, есть код, в строку вбивается слово. Нужно в строке найти группы слов, имеющие одинаковый состав букв (количество одинаковых букв не имеет значения), слова выводить в порядке их вхождения в строку. Ну например в строке идут слова: abba abaa abca ab abc, затем идет разделение по строкам, в первую строку идут abba abaa и ab, так как состав букв одинаковый, затем новая строчка: abca abc. Ну... как-то так, мне бы хотя бы узнать как поиск реализуется. Очень нужно, буду благодарен.

Код: Выделить всё

#include "stdafx.h"
#include <string.h>
#include <stdio.h>

void main()
{
char str[81]; // Исходная строка

gets(str);

char copy_str[81]; // копия строки, чтобы не портить исходную
strcpy(copy_str,str); // делаем копию

char *razdel=" \n\t\r\".,!?"; // Разделители слов (для разбивки) 
char *word; // очередное слово строки

word=strtok(copy_str,razdel); // получаем первое слово

while(word)
{
printf("%s\n", word); // печатаем очередное слово
word=strtok(NULL,razdel); // далее (с текущего места в строке) - получаем следующее слово
}

getch();

}

Приходит в голову следующий подход.

Код: Выделить всё

#include <map>
#include <vector>
#include <string>
#include <algorithm>

// динамический массив строк
typedef std::vector<std::string> vec_strs;
// map с ключом строкой и с вектором строк в качестве значения
typedef std::map< std::string, vec_strs > map_str2vec_strs;

// объявление переменной такого типа
map_str2vec_strs mapSortedWords;

В цикле по всем словам (предложенный цикл через strtok тоже подходит) мы делаем следующее для каждого слова:

1. Строим ключ для слова. Ключ строится путём отбрасывания неуникальных букв. Используя STL, это будет выглядеть так:

Код: Выделить всё

std::string strOneWord = word;
std::sort(strOneWord.begin(), strOneWord,end());
strOneWord.erase(std::unique(strOneWord.begin(), strOneWord.end()), strOneWord.end());

2. Затем получаем из map по построенному ключу вектор слов, который ассоциирован с этим ключом. Если в map вектора с таким ключом ещё нету, то он будет автоматически создан:

Код: Выделить всё

std::vector<std::string>& vecWordsByKey = mapSortedWords[strOneWord];

3. Записываем неизмённое изначальное слово в конец вектора слов.

Код: Выделить всё

vecWordsByKey.push_back(word);

4. Ну и последнее, что нам осталось сделать - это в конце, после завершения основного цикла, вывести нашу построенную map:

Код: Выделить всё


map_str2vec_strs::const_iterator it = mapSortedWords.begin();
for (; it != mapSortedWords.end(); ++it)
{
   // итератор указывает на пару (ключ - значение)   
   const std::string& strKey = (*it).first;
   const vec_strs& vecWordsByKey = (*it).second;

   // сначала печатаем ключ и ставим двоеточие
   printf("%s: ", strKey.c_str());
   // затем в цикле выводим все слова, которые ему соответствуют через пробел
   vec_strs::const_iterator itWord = vecWordsByKey.begin();
   for (; itWord != vecWordsByKey.end(); ++itWord)
   {
      // итератор указывает на строку
      const std::string& strWord = *itWord;
      printf("%s ", strWord.c_str());
   }
   
   // перевод на следующую строку
   printf("\n");
}

Developing.ru

Помогите найти слова с одинаковым составом букв

Помогите найти слова с одинаковым составом букв

Re: Помогите найти слова с одинаковым составом букв