C++ Поиск анаграмм в словах

Question

Я работаю над программой, которая смотрит, является ли конкретное слово анаграммой, используя std:count, однако я не думаю, что моя функциональная логика правильная, и я не могу понять ее.

Предположим, есть следующие слова в файле:

Evil 
Vile 
Veil 
Live 

Мой код выглядит следующим образом:

#include <iostream> 
#include <vector> 
#include <fstream> 
#include <map> 
using namespace std; 

struct Compare { 
std::string str; 
Compare(const std::string& str) : str(str) {} 
}; 

bool operator==(const std::pair<int, std::string>&p, const Compare& c) { 
return c.str == p.second; 
} 
    bool operator==(const Compare& c, const std::pair<int, std::string>&p) { 
    return c.str == p.second; 
} 

std::vector<std::string> readInput(ifstream& file) 
{ 
std::vector<std::string> temp; 

string word; 

while (file >> word) 
{ 
    temp.push_back(word); 
} 
std::sort(temp.begin(), temp.end()); 

return temp; 
} 

int main(int argc, char *argv[]) { 

string file = "testing.txt"; 
ifstream ss(file.c_str()); 

if(!ss.is_open()) 
{ 
    cerr << "Cannot open the text file"; 
} 

std::vector<std::string> words = readInput(ss); 

std::map<int, std::string> wordsMap; 

//std::map<std::string value, int key> values; 

for(unsigned i=0; (i < words.size()); i++) 
{ 
    wordsMap[i] = words[i]; 
} 


int count = std::count(wordsMap.begin(), wordsMap.end(), Compare("Evil")); 
cout << count << endl; 
} 

Я уверен, что это просто случай моей логики неправильно в функции. Надеюсь, кто-то может помочь :)

Answer 1

Самый простой подход был бы

Чтобы проверить, как следующее (псевдокод)

bool isAnagram(string s, string t) {return sort(s) == sort(t); }

Таким образом, использовать некоторые думают, как следующая, не нуждается в std::map

struct Compare { 
std::string str; 
Compare(const std::string& x) : str(x) { 
    std::sort(str.begin(),str.end()); std::transform(str.begin(), 
    str.end(),str.begin(), ::toupper);} 

    bool operator()(const std::string& t) 
    { 
     std::string s= t; 
     std::transform(s.begin(), s.end(),s.begin(), ::toupper); 
     std::sort(s.begin(),s.end()); 

    return s == str; 
    } 
}; 

А потом

int count = std::count_if(words.begin(), words.end(), Compare("Evil"));

См HERE

Answer 2

EDIT: Кажется, в вашем нынешнем коде вы проверяете, соответствуют ли строки точно друг другу (а не анаграммы).

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

Например, для зла, то массив будет:

0,0,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0. // It has 1's for letters e,v,i and l 
a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z 

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

Теперь вам нужно только посмотреть, какие слова имеют тот же самый соответствующий массив.

Если вы хотите сравнить все N слов поровну, вы можете сделать это, используя две вложенные петли в сложности O (N^2).
Сложность сравнения одной пары - O (1).
Сложность создания массивов = O (L), где L - длина строки.

Answer 3

Это не самый эффективный алгоритм, но быстро изменить вашу программу, которая будет работать может быть:

bool operator==(const std::pair<int, std::string>&p, const Compare& c) { 
    std::string a = c.str; 
    std::transform(a.begin(), a.end(), a.begin(), ::tolower); 
    std::sort(a.begin(), a.end()); 

    std::string b = p.second; 
    std::transform(b.begin(), b.end(), b.begin(), ::tolower); 
    std::sort(b.begin(), b.end()); 

    return a == b; 
} 

Answer 4

Рассмотрим следующий пример:

map<string, set<string>> anagrams; 

for (auto word : words) 
    anagrams[sort(word)].insert(word); 

const set<string>& find_anagrams(const string& word) 
{ 
    return anagrams[word]; 
} 

Answer 5

Если у вас есть много слов, которые являются относительно короткими (или если вы можете работать с большими номер ЛИЭС), то вы можете использовать решение, похожее на то, что я здесь написал -

Generate same unique hash code for all anagrams

По существу - отобразить каждый символ уникального простого числа (не должен быть большим, вы можете отобразить цельный ABC в простые числа до 101), и для каждого слова умножайте числа, полученные от него, символы. Поскольку умножение является коммутативным, анаграммы будут давать одинаковый результат, поэтому вы просто сравниваете этот результат, хешируете его или делаете все, что хотите.

Имейте в виду, что для длинных слов значения будут расти довольно быстро, поэтому вам может понадобиться big numbers lib