Расстояние между строками, только транспозиции [дубликат]

На этот вопрос уже есть ответы здесь :

Закрыт 8 лет назад .

Возможный дубликат:
Подсчет свопов, необходимых для преобразования одной перестановки в другую

Я ищу алгоритм, который бы подсчитывал какое-то расстояние между строками, где разрешена только операция транспонирования двух соседних символов. Например:
строка1: "мать"
строка2: "moterh"
расстояние: 2 (сначала замените "h" на "e" и получите "motehr", а затем "h" с "r", что приведет к "moterh")
Я знаю, что расстояние Дамерау – Левенштейна очень похоже на эту проблему, но требует много памяти (I ' хотелось бы, чтобы он достаточно быстро работал со словами до 1 000 000 символов). Я уже писал это:

int amo = 0;

for (int i = 0; i < n; i++)
{
    if (fromString[i] == toString[i])
        continue;
    char toWhat = toString[i];
    int where = -1;
    for (int j = i; j < n; j++)
    {
        if (fromString[j] == toWhat)
        {
            where = j;
            break;
        }
    }
    while (where != i)
    {
        char temp = fromString[where];
        fromString[where] = fromString[where - 1];
        fromString[where - 1] = temp;
        where--;
        amo++;
    }
}
cout << amo << endl;`

Строки представлены как char [n], где n - их длина. Я совершенно уверен, что есть способ сделать это быстрее, и был бы очень благодарен, если кто-нибудь подскажет мне, как это сделать, или напишет какой-нибудь исходный код (лучше всего будет Java / Python / C ++, но все будет хорошо).

P.S. Извините за языковые ошибки, я не англичанин и еще не освоил этот язык.

задан Community 23 May 2017 в 12:31

0 ответов

Другие вопросы по тегам:

string algorithm dynamic-programming levenshtein-distance edit-distance

Расстояние между строками, только транспозиции [дубликат]

0 ответов

Похожие вопросы: