TaskC

#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <sstream>
#include <iostream>


using std::cout;
using std::string;
using std::cin;
using std::endl;
using std::vector;


int Wagner_Fischer_for_Damerau_Levenshtein(string& s, string& t)
{
    int n = s.length() + 1;
    int m = t.length() + 1;
    int** d = new int* [n];
    for (int i = 0; i < n; ++i)
    {
        d[i] = new int[m];
        d[i][0] = i;
    }
    for (int j = 1; j < m; ++j)
        d[0][j] = j;

    for (int i = 1; i < n; ++i)
    {
        for (int j = 1; j < m; ++j)
        {
            if (s[i - 1] == t[j - 1])
                d[i][j] = d[i - 1][j - 1];
            else if (i > 1 && j > 1 && s[i - 1] == t[j - 2] && s[i - 2] == t[j - 1])
                d[i][j] = std::min(d[i - 1][j] + 1,
                    std::min(d[i][j - 1] + 1,
                        std::min(d[i - 1][j - 1] + 1,
                            d[i - 2][j - 2] + 1)));
            else
                d[i][j] = std::min(d[i - 1][j] + 1,
                    std::min(d[i][j - 1] + 1,
                        d[i - 1][j - 1] + 1));
        }
    }
    int result = d[n - 1][m - 1];
    for (int i = 0; i < n; ++i)
        delete[] d[i];
    delete[] d;
    return result;
}

int main()
{
    int n;
    cin >> n;
    cin.ignore();
    string word, word2;
    bool check = false;
    string* dict = new string[n];
    vector<string> res;
    for (int i = 0; i < n; i++)
    {
        getline(cin, word);
        for (int i = 0; i < word.size(); i++)
        {
            if (word[i] == -114)
                word[i] = word[i] + 32;
            else
            {
                if (word[i] <= -97 && word[i] >= -128)
                    word[i] = word[i] + 80;
                if (word[i] <= 'Z' && word[i] >= 'A')
                    word[i] = tolower(word[i]);
            }
        }
        dict[i] = word;
    }
    while (!cin.fail())
    {
        check = false;
        getline(cin, word);
        if (word != "")
        {
            word2 = word;
            for (int i = 0; i < word2.size(); i++)
            {
                if (word2[i] == -114)
                    word2[i] = word2[i] + 32;
                else
                {
                    if (word2[i] <= -97 && word2[i] >= -128)
                        word2[i] = word2[i] + 80;
                    if (word2[i] <= 'Z' && word2[i] >= 'A')
                        word2[i] = tolower(word2[i]);
                }
            }
            for (int i = 0; i < n; i++)
                if (dict[i] == word2)
                {
                    cout << word << " - ok" << endl;
                    check = true;
                    break;
                }
            if (!check)
            {
                for (int i = 0; i < n; i++)
                    if (Wagner_Fischer_for_Damerau_Levenshtein(dict[i], word2) == 1)
                        res.push_back(dict[i]);
                if (res.empty())
                    cout << word << " -?" << endl;
                else if (res.size() == 1)
                    cout << word << " -> " << res[0] << endl;
                else
                {
                    sort(res.begin(), res.end());
                    cout << word << " -> ";
                    for (int i = 0; i < res.size() - 1; i++)
                        cout << res[i] << ", ";
                    cout << res[res.size() - 1] << endl;
                }
                res.clear();
            }
        }
    }
    delete[] dict;
    return 0;
}