Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <string>
- #include <set>
- #include <algorithm>
- #include <sstream>
- #include <locale>
- #include <iostream>
- #include <Windows.h>
- using std::cout;
- using std::string;
- using std::cin;
- using std::endl;
- using std::vector;
- using std::pair;
- using namespace std;
- 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] = min(d[i - 1][j] + 1,
- min(d[i][j - 1] + 1,
- min(d[i - 1][j - 1] + 1,
- d[i - 2][j - 2] + 1)));
- else
- d[i][j] = min(d[i - 1][j] + 1,
- 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()
- {
- SetConsoleCP(1251);
- SetConsoleOutputCP(1251);
- 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] <= 'Я' && word[i] >= 'А')
- word[i] = word[i] - 'А' + 'а';
- 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 < word.size(); i++)
- {
- if (word2[i] <= 'Я' && word2[i] >= 'А')
- word2[i] = word2[i] - 'А' + 'а';
- 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();
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement