5

我有一个单词列表和一个包含许多字谜的文件。这些字谜是在单词列表中找到的单词。我需要开发一种算法来查找匹配的单词并将它们生成在输出文件中。到目前为止，我开发的代码仅适用于前两个单词。此外，我无法让代码与其中任何地方包含数字的字符串一起玩得很好。请告诉我如何修复代码。

#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

试图改进米奇小麦的解决方案：

  • 存储排序顺序和单词实际上是没有必要的 - 只存储列表中每个单词的排序字符串。

  • 无论如何，当我们从文件中读取一个单词时，我们必须对其进行排序以查找它是否等于已排序的字符串 - 并且索引是在已排序的字符串上建立索引的，因此无论如何它都无济于事。

  1. 用单词列表中的单词构建一个“位置无关”的散列 - 还将排序的字符串存储在散列中。

  2. 对于文件中的每个单词，获取“位置无关”哈希并签入哈希表。

  3. 如果命中，则排序并与存储在哈希中此位置的每个排序字符串进行比较（冲突！）。

想法？

于 2011-08-09T18:28:30.287 回答