5

単語リストと、多数のアナグラムを含むファイルがあります。これらのアナグラムは、単語リストにある単語です。一致する単語を見つけて出力ファイルに生成するアルゴリズムを開発する必要があります。これまでに開発したコードは、最初の 2 つの単語に対してのみ機能しました。さらに、コードのどこかに数字を含む文字列をうまく処理するコードを取得できません。コードを修正する方法を教えてください。

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main (void)
{
int x = 0, y = 0;
int a = 0, b = 0;
int emptyx, emptyy;
int match = 0;
ifstream f1, f2;
ofstream f3;
string line, line1[1500], line2[50];
size_t found;

f1.open ("wordlist.txt");
f2.open ("file.txt");
f3.open ("output.txt");

while (f1.eof() == 0)
{
    getline (f1, line);
    line1[x] = line;
    x++;
}

while (f2.eof() == 0)
{
    getline (f2, line);
    line2[y] = line;
    y++;
}

//finds position of last elements
emptyx = x-1;
emptyy = y-1;

//matching algorithm
for (y = 0; y <= emptyy; y++)
{
    for (x = 0; x <= emptyx; x++)
    {
        if (line2[y].length() == line1[x].length())
        {
            for (a = 0; a < line1[x].length(); a++)
            {
                found = line2[y].find(line1[x][a]);
                if (found != string::npos)
                {
                    match++;
                    line2[y].replace(found, 1, 1, '.');

                    if (match == line1[x].length())
                    {
                        f3 << line1[x] << ", ";
                        match = 0;
                    }
                }
            }
        }
    }
}

f1.close();
f2.close();
f3.close();

return 0;
}
4

2 に答える 2

6

ステップ 1: 単語リスト内の各単語の並べ替えられた文字のキーと、その単語を値とするインデックスを作成します。

act   -  cat
act   -  act
dgo   -  dog

...

aeeilnppp - pineapple

....

etc...

ステップ 2: 検索するアナグラムごとに、アナグラム単語の文字を並べ替え、インデックスと照合して、並べ替えられたキーが一致するインデックスからすべての単語を取得します。

于 2011-06-21T08:53:40.153 に答える
3

Mitch Wheat のソリューションを改善しようとしています:

  • 並べ替えられた順序と単語の両方を保存する必要はありません。リスト内のすべての単語について、並べ替えられた文字列のみを保存します。

  • とにかく、ファイルから単語を読み取るとき、それがソートされた文字列と等しいかどうかを確認するためにソートする必要があります-インデックスはソートされた文字列にインデックス付けされているため、とにかく役に立ちません.

  1. 単語リスト内の単語を使用して「位置に依存しない」ハッシュを作成します。また、ソートされた文字列をハッシュに格納します。

  2. ファイル内のすべての単語について、「位置に依存しない」ハッシュを取得し、ハッシュテーブルにチェックインします。

  3. ヒットした場合、ソートして、ハッシュ内のこの位置に格納されているすべてのソート済み文字列と比較します (衝突!)。

考え？

于 2011-08-09T18:28:30.287 に答える