Поиск анаграмм - C++ - Ответ 2074437

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
 
/* определяет равенство строк по количеству вхождений каждой *
 * буквы в эту строку. пробелы цифры и пр. игнорируются      */
bool letter_cmp( const std::string &a, const std::string &b )
{
    unsigned count_a[ 'z' - 'a' + 1 ] = {0}; // количество вхождений букв в строку а
    unsigned count_b[ 'z' - 'a' + 1 ] = {0}; // количество вхождений букв в строку b
 
    // считаем a
    for( int i = 0; i < a.size(); i++ )
    {
        if( isalpha( a[i] ) )
           count_a[ 'z' - tolower( a[i] ) ]++;
    }
 
    // считаем b
    for( int i = 0; i < b.size(); i++ )
    {
        if( isalpha( b[i] ) )
           count_b[ 'z' - tolower( b[i] ) ]++;
    }
 
    // проверяем равенство вхождений каждой буквы
    for( int i = 0; i < 'z' - 'a'; i++ )
    {
        if( count_a[i] != count_b[i] )
           return false; // если количество вхождений этой буквы отличается, возвращаем false
    }
 
    return true; // если все вхождения равны, возвращаем true
}
 
int main()
{
    std::vector<std::string> lines; // здесь хранятся строки файла
    std::string input; // сюда вводится новая строка из файла
 
    // ---------- читаем весь файл ---------
    std::ifstream fs( "in.txt" );
 
    if( !fs.is_open() )
    {
       std::cerr << "error opening in.txt\n";
       return -1;
    }
 
    while( fs >> input )
       lines.push_back( input );
 
    fs.close();
 
    std::cout << "done reading " << lines.size() << " words\n\n";
 
    // ---- заполняем вектор связности -----
    std::vector<int> connectivity( lines.size() );
 
    for( int i = 0; i < lines.size(); i++ )
       connectivity[i] = i;
 
    // ---- определяем связность -----------
 
    for( int i = 0; i < lines.size(); i++ ) // проходим все строки
    {
        for( int u = 0; u < lines.size(); u++ ) // n*n раз
        {
            if( connectivity[i] != connectivity[u] ) // если эти две строки уже связаны, пропускаем их
            {
                if( letter_cmp( lines[i], lines[u] ) ) // иначе если строки равны по количеству вхождений букв
                {
                    // связываем их
                    int old_i = connectivity[i]; // старое значение ключа
 
                    for( int j = 0; j < connectivity.size(); j++ )
                    {
                        if( connectivity[j] == old_i ) // везде, где ключ старый
                           connectivity[j] = connectivity[u]; // меняем его на новый
                    }
                }
            }
        }
    }
 
    // ---- выводим все связанные слова ------
    for( int i = 0; i < connectivity.size(); i++ )
    {
        unsigned int out = 0;
 
        if( std::count( connectivity.begin(), connectivity.end(), i ) > 1 )
        {
            for( int u = 0; u < connectivity.size(); u++ )
            {
               if( connectivity[u] == i )
               {
                  if( out )
                     std::cout << ", ";
 
                  std::cout << lines[u];
                  out++;
               }
            }
 
            if( out )
               std::cout << '\n';
        }
    }
 
    return 0;
}