Нахождение анаграмм в списке слов - PullRequest
Новая
       4

Нахождение анаграмм в списке слов

5 голосов
/ 21 июня 2011

У меня есть список слов и файл, содержащий несколько анаграмм.Эти анаграммы являются словами, найденными в списке слов.Мне нужно разработать алгоритм, чтобы найти подходящие слова и вывести их в выходной файл.Код, который я разработал до сих пор, работал только для первых двух слов.Кроме того, я не могу заставить код хорошо играть со строками, содержащими числа где-либо в нем.Подскажите пожалуйста, как мне исправить код. 

#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;
}

Ответы [ 2 ]

6 голосов
/ 21 июня 2011

Шаг 1: Постройте индекс с ключом отсортированных символов в каждом слове в списке слов и со значением, являющимся словом. 

act   -  cat
act   -  act
dgo   -  dog

...

aeeilnppp - pineapple

....

etc...

Шаг 2. Для каждой анаграммы, которую вы хотите найти, отсортируйте символы в слове анаграммы, а затем сопоставьте с индексом, чтобы получить все слова из индекса с соответствующим отсортированным ключом.

3 голосов
/ 09 августа 2011

Попытка улучшить решение Mitch Wheat:

  • Хранить отсортированный порядок и слово действительно не нужно - сохраняйте только отсортированную строку для каждого слова в списке.

  • В любом случае, когда мы читаем слово из файла, мы должны отсортировать его, чтобы найти, равно ли оно отсортированной строке - и индекс проиндексирован на отсортированной строке, так что в любом случае это не поможет.

  1. Создайте 'независимый от позиции' хэш со словами в списке слов - также сохраните отсортированную строку в хеш.

  2. Для каждого слова в файле получите хэш «независимый от позиции» и зарегистрируйте хеш-таблицу.

  3. При попадании сортируйте и сравнивайте каждую отсортированную строку, сохраненную в этой позиции в хеш-коде (коллизии!).

Мысли?

...