Advertisement
AmidamaruZXC

Untitled

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