Advertisement
AmidamaruZXC

Untitled

Nov 30th, 2020
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.06 KB | None | 0 0
  1. #include <vector>
  2. #include <string>
  3. #include <set>
  4. #include <algorithm>
  5. #include <sstream>
  6. #include <iostream>
  7.  
  8.  
  9. using std::cout;
  10. using std::string;
  11. using std::cin;
  12. using std::endl;
  13. using std::vector;
  14. using std::pair;
  15.  
  16. using namespace std;
  17.  
  18.  
  19. int Wagner_Fischer_for_Damerau_Levenshtein(string& s, string& t)
  20. {
  21.     int n = s.length() + 1;
  22.     int m = t.length() + 1;
  23.     int** d = new int* [n];
  24.     for (int i = 0; i < n; ++i)
  25.     {
  26.         d[i] = new int[m];
  27.         d[i][0] = i;
  28.     }
  29.     for (int j = 1; j < m; ++j)
  30.         d[0][j] = j;
  31.  
  32.     for (int i = 1; i < n; ++i)
  33.     {
  34.         for (int j = 1; j < m; ++j)
  35.         {
  36.             if (s[i - 1] == t[j - 1])
  37.                 d[i][j] = d[i - 1][j - 1];
  38.             else if (i > 1 && j > 1 && s[i - 1] == t[j - 2] && s[i - 2] == t[j - 1])
  39.                 d[i][j] = min(d[i - 1][j] + 1,
  40.                     min(d[i][j - 1] + 1,
  41.                         min(d[i - 1][j - 1] + 1,
  42.                             d[i - 2][j - 2] + 1)));
  43.             else
  44.                 d[i][j] = min(d[i - 1][j] + 1,
  45.                     min(d[i][j - 1] + 1,
  46.                         d[i - 1][j - 1] + 1));
  47.         }
  48.     }
  49.     int result = d[n - 1][m - 1];
  50.     for (int i = 0; i < n; ++i)
  51.         delete[] d[i];
  52.     delete[] d;
  53.     return result;
  54. }
  55.  
  56. int main()
  57. {
  58.     int n;
  59.     cin >> n;
  60.     cin.ignore();
  61.     string word;
  62.     bool check = false;
  63.     string* dict = new string[n];
  64.     vector<string> res;
  65.     for (int i = 0; i < n; i++)
  66.     {
  67.         getline(cin, word);
  68.         dict[i] = word;
  69.     }
  70.     while (!cin.fail())
  71.     {
  72.         check = false;
  73.         getline(cin, word);
  74.         if (word != "")
  75.         {
  76.             for (int i = 0; i < n; i++)
  77.                 if (dict[i] == word)
  78.                 {
  79.                     cout << word << " - ok" << endl;
  80.                     check = true;
  81.                     break;
  82.                 }
  83.             if (!check)
  84.             {
  85.                 for (int i = 0; i < n; i++)
  86.                     if (Wagner_Fischer_for_Damerau_Levenshtein(dict[i], word) == 1)
  87.                         res.push_back(dict[i]);
  88.                 if (res.empty())
  89.                     cout << word << " -?" << endl;
  90.                 else if (res.size() == 1)
  91.                     cout << word << " -> " << res[0] << endl;
  92.                 else
  93.                 {
  94.                     sort(res.begin(), res.end());
  95.                     cout << word << " -> ";
  96.                     for (int i = 0; i < res.size() - 1; i++)
  97.                         cout << res[i] << ", ";
  98.                     cout << res[res.size() - 1] << endl;
  99.                 }
  100.                 res.clear();
  101.             }
  102.         }
  103.     }
  104.  
  105.     return 0;
  106. }
  107.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement