Yam Code

New Paste Browse

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <fstream>
using namespace std;

vector<vector<char>> collection;

struct Node {
    Node* child[26]; // alphabet size
    bool isEnd;
};

Node* getNode() {
    Node* p = new Node;
    p->isEnd = false;
    for (int i = 0; i < 26; i++) {
        p->child[i] = nullptr; // Create a new 26 -subtree incase a new letter come in
    }
    return p;
}

void insert(Node* root, string input) {
    Node* p = root;

for (int i = 0; i < input.length(); i++)
    {
        int index = input[i] - 'a';
        if (!p->child[index])// If the node is not present in this tree, create a new Node 
            p->child[index] = getNode();
        p = p->child[index];
    }
    p->isEnd = true;
}

bool search(struct Node* root, string input)
{
    struct Node* p = root;

for (int i = 0; i < input.length(); i++)
    {
        int index = input[i] - 'a';
        if (!p->child[index]) // If a single char in input not in trie, return false from this
            return false;
        p = p->child[index];// Check the next char
    }

return (p != NULL && p->isEnd);
}

void Initialize(Node*& root, string FileNameDict) {
    ifstream file(FileNameDict);
    if (!file) {
        return;
    }
    else {
        string temp;
        while (!file.eof()) {
            getline(file, temp);
            if (temp == "") {
                break;
            }
            insert(root, temp);
        }
    }
}

bool checkIfExist(vector<vector<char>> src, vector<char> c, int j) {
    for (int i = 0; i < j; i++){
        if (src[i] == c)
            return true;
    }
    return false;
}

bool check(vector<char> src, char c) {
    for (int i = 0; i < src.size() - 1; i++)
    {
        if (src[i] == c)
            return true;
    }
    return false;
}

void generate(vector<char> lt, vector<char> res, int k, int i) {
    unsigned j;
    for (j = i; j <= lt.size() - k + i; j++) {
        if (i == k) {
            sort(res.begin(),res.begin() + k);
            collection.push_back(res);
            return;
        }
        res.push_back(lt[j]);
        if (res.size() > 1 && check(res, lt[j])) {
            res.pop_back();
            continue;
        }
        generate(lt, res, k, i + 1);
        res.pop_back();
    }
}

void removeDuplicate(vector<vector<char>>& src) {
    for (int i = src.size() - 1; i > 0; i--){
        if (checkIfExist(src, src[i], i))
            src.erase(src.begin() + i);
    }
}

void permute(string str, string out, vector<string>& des)
{
    if (str.size() == 0) {
        des.push_back(out);
        return;
    }

for (int i = 0; i < str.size(); i++) {
        permute(str.substr(1), out + str[0], des);
        rotate(str.begin(), str.begin() + 1, str.end());
    }
}

string ToString(vector<char> src) {
    string temp = "";
    for (int i = 0; i < src.size(); i++)
    {
        temp += src[i];
    }
    return temp;
}

int main() {
    Node* root = getNode();
    Initialize(root, "Dic.txt");
    string temp;
    getline(cin, temp);
    vector<char> letter;
    for (int i = 0; i < temp.size(); ++i)
        if (temp[i] != ' ')
            letter.push_back(temp[i]);
    vector<char> res;
    vector<string> ans;
    for (int i = 3; i <= letter.size(); i++)
    {
        generate(letter, res, i, 0);
        removeDuplicate(collection);
        for (int i = 0; i < collection.size(); i++)
        {
            vector<string> all_permute;
            permute(ToString(collection[i]), "", all_permute);
            for (int i = 0; i < all_permute.size(); i++)
            {
                if (search(root, all_permute[i]))
                    ans.push_back(all_permute[i]);
            }
            all_permute.clear();
        }
        collection.clear();
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << endl;
    return 0;
}

Paste Settings

Paste Title : [Optional]

Paste Folder : [Optional]

Syntax Highlighting : [Optional]

Paste Expiration : [Optional]

Paste Status : [Optional]

Password : [Optional]

Description: [Optional]

Tags: [Optional]

Encrypt Paste (?)

You are currently not logged in, this means you can not edit or delete anything you paste. Sign Up or Login

Paste Settings

Site Languages