DS_Homework_5

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct Node {
    Node() {
    }
    Node(char character) {
        this->Character = character;
    }
    char Character = '\0';
    bool WordEnd = false;
    vector<Node> Nodes;
};

void findAllChanges(string s, vector<string>& l) {
    for (int i = 0; i <= s.size(); i++) {
        if (i >= 1) {
            l.push_back(s.substr(0, i - 1) + s.substr(i));
            l.push_back(s.substr(0, i - 1) + '?' + s.substr(i));
        }
        l.push_back(s.substr(0, i) + '?' + s.substr(i));
        if (i + 1 < s.size()) {
            l.push_back(s.substr(0, i) + s[i + 1] + s[i] + s.substr(i + 2));
        }
    }
}

void traverse(Node& n, const string& s, int index, vector<string>& l) {
    if (s.size() == index) {
        if (n.WordEnd) {
            l.push_back(s);
        }
        return;
    }
    for (int i = 0; i < n.Nodes.size(); i++) {
        if (n.Nodes[i].Character == s[index]) {
            traverse(n.Nodes[i], s, index + 1, l);
        }
        else if (s[index] == '?' && n.Nodes[i].Character >= 'a' && n.Nodes[i].Character <= 'z') {
            traverse(n.Nodes[i], s.substr(0, index) + n.Nodes[i].Character + (s.size() == index + 1 ? "" : s.substr(index + 1)), index + 1, l);
        }
    }
}

int main() {
    fstream dictStream = fstream("dictionary.txt", ios::in);
    fstream inputStream = fstream("input.txt", ios::in);
    fstream outputStream = fstream("output.txt", ios::out);
    outputStream << "word,answer" << '\n';

    Node tree;

    string line;
    while (getline(dictStream, line)) {
        if (line.size() == 0 || line[0] == ';') {
            continue;
        }
        Node* nodeRef = nullptr;
        auto startNodeIter = find_if(tree.Nodes.begin(), tree.Nodes.end(), [&](const Node& n) {return n.Character == line[0]; });
        if (startNodeIter != tree.Nodes.end()) {
            nodeRef = &*startNodeIter;
        }
        else {
            tree.Nodes.push_back(Node(line[0]));
            nodeRef = &*(tree.Nodes.end() - 1);
        }
        for (int i = 1; i < line.size(); i++) {
            auto nextNodeIter = find_if(nodeRef->Nodes.begin(), nodeRef->Nodes.end(), [&](const Node& n) {return n.Character == line[i]; });
            if (nextNodeIter != nodeRef->Nodes.end()) {
                nodeRef = &*nextNodeIter;
            }
            else {
                nodeRef->Nodes.push_back(Node(line[i]));
                nodeRef = &*(nodeRef->Nodes.end() - 1);
            }
        }
        nodeRef->WordEnd = true;
    }


    while (getline(inputStream, line)) {
        vector<string> foundWords = vector<string>();
        outputStream << line << ",";
        traverse(tree, line, 0, foundWords);
        if (foundWords.size() > 0) {
            outputStream << "OK\n";
        }
        else {
            vector<string> changes = vector<string>();
            findAllChanges(line, changes);
            int prevChgSize = changes.size();
            for (int i = 0; i < prevChgSize; i++) {
                findAllChanges(changes[i], changes);
            }
            sort(changes.begin(), changes.end());
            for (int i = 0; i < changes.size(); i++) {
                if (i + 1 < changes.size() && changes[i] == changes[i + 1]) {
                    continue;
                }
                traverse(tree, changes[i], 0, foundWords);
            }
            sort(foundWords.begin(), foundWords.end());
            //cout << line << "\t" ;
            //for (int i = 0; i < foundWords.size(); i++) {
            //  cout << foundWords[i] << " ";
            //}
            //cout << endl;
            if (foundWords.size() > 0) {
                for (int i = 0; i < foundWords.size() - 1; i++) {
                    if (foundWords[i] == foundWords[i + 1]) {
                        continue;
                    }
                    outputStream << foundWords[i] << " ";
                }
                outputStream << foundWords[foundWords.size() - 1] << "\n";
            }
            else {
                outputStream << "NONE\n";
            }
        }
    }

    outputStream.close();
}