Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <sstream>
- #include <iostream>
- using namespace std;
- int max(int a, int b) { return (a > b) ? a : b; }
- int min(int a, int b) { return (a < b) ? a : b; }
- int Solve(string& str1, string& str2)
- {
- int n = str1.length() + 1;
- int m = str2.length() + 1;
- vector<vector<int>> distance(n, vector<int>(m));
- for (int i = 0; i < n; ++i)
- distance[i][0] = i;
- for (int j = 1; j < m; ++j)
- distance[0][j] = j;
- for (int i = 1; i < n; ++i)
- for (int j = 1; j < m; ++j)
- {
- if (str1[i - 1] == str2[j - 1])
- distance[i][j] = distance[i - 1][j - 1];
- else if (i > 1 && j > 1 && str1[i - 1] == str2[j - 2] && str1[i - 2] == str2[j - 1])
- distance[i][j] = min(distance[i - 1][j] + 1, min(distance[i][j - 1] + 1, min(distance[i - 1][j - 1] + 1, distance[i - 2][j - 2] + 1)));
- else
- distance[i][j] = min(distance[i - 1][j] + 1, min(distance[i][j - 1] + 1, distance[i - 1][j - 1] + 1));
- }
- return distance[n - 1][m - 1];
- }
- void input(vector<string>& dictionary, vector<string>& words1, vector<string>& words2)
- {
- string word1, word2;
- getline(cin, word1);
- int n = stoi(word1);
- for (int i = 0; i < n; ++i)
- {
- getline(cin, word1);
- for (int i = 0; i < word1.size(); ++i)
- {
- if (word1[i] == -114)
- word1[i] = word1[i] + 32;
- else
- {
- if (word1[i] <= -97 && word1[i] >= -128)
- word1[i] = word1[i] + 80;
- else if (word1[i] <= 'Z' && word1[i] >= 'A')
- word1[i] = tolower(word1[i]);
- }
- }
- dictionary.push_back(word1);
- }
- while (!cin.fail())
- {
- getline(cin, word1);
- if (word1 != "")
- {
- word2 = word1;
- 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]);
- }
- }
- words1.push_back(word1);
- words2.push_back(word2);
- }
- }
- }
- void output(vector<string> dictionary, vector<string> words1, vector<string> words2)
- {
- vector<string> answer;
- bool check;
- for (int i = 0; i < words1.size(); ++i)
- {
- check = false;
- for (int j = 0; j < dictionary.size(); ++j)
- if (dictionary[j] == words2[i])
- {
- cout << words1[i] << " - ok" << endl;
- check = true;
- break;
- }
- if (!check)
- {
- for (int j = 0; j < dictionary.size(); ++j)
- if (Solve(dictionary[j], words2[i]) == 1)
- answer.push_back(dictionary[j]);
- if (answer.empty())
- cout << words1[i] << " -?" << endl;
- else if (answer.size() == 1)
- cout << words1[i] << " -> " << answer[0] << endl;
- else
- {
- sort(answer.begin(), answer.end());
- cout << words1[i] << " -> ";
- for (int k = 0; k < answer.size() - 1; ++k)
- cout << answer[k] << ", ";
- cout << answer[answer.size() - 1] << endl;
- }
- answer.clear();
- }
- }
- }
- int main()
- {
- vector<string> dictionary;
- vector<string> words1, words2;
- input(dictionary, words1, words2);
- output(dictionary, words1, words2);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement