1

特定の単語がアナグラムであるかどうかを調べるプログラムに取り組んで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;
}

関数のロジックが間違っているだけだと確信しています。誰かが助けてくれることを願っています:)

4

5 に答える 5

1

編集:現在のコードでは、文字列が互いに正確に等しい(アナグラムではない)かどうかをチェックしているようです。

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) の複雑さで 2 つのネストされたループを使用して比較できます。
1 つのペアを比較するための複雑さは O(1) です。
配列の作成の複雑さ = O(L) ここで、L は文字列の長さです。

于 2013-09-16T17:53:57.197 に答える
0

比較的短い単語がたくさんある場合 (または多数のライブラリを操作できる場合)、ここに書いたのと同様の解決策を使用できます -

すべてのアナグラムに対して同じ一意のハッシュ コードを生成する

基本的に - 各文字を一意の素数にマップし (大きくする必要はありません。ABC 全体を 101 までの素数にマップできます)、単語ごとにその文字から受け取った素数を乗算します。乗算は交換可能であるため、アナグラムは同じ結果を返すため、その結果を比較したり、ハッシュしたり、やりたいことをしたりするだけです

長い単語の場合、値が急速に大きくなるため、大きな数値ライブラリが必要になる場合があることに注意してください

于 2013-09-17T12:20:27.320 に答える