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);
        }
    }
}

// Function to generate all letter combination
void generate(vector<char> src, int a[], char res[], int k, int i) { 
    int j;
    for (j = a[i - 1] + 1; j <= src.size() - k + i; j++) // any j has condition: a[i-1] + 1 <= j <= size of source - k + i
    {
        a[i] = j;
        res[i] = src[j - 1]; // assign letter in input to char array
        if (i == k) { // stop condition (if i = k mean enough letter for a combination)
            vector<char> temp; // temp vector to save char array
            for (int l = 1; l <= k; ++l)
                temp.push_back(res[l]);
            collection.push_back(temp); // push temp vector to the collection
        }
        else {
            generate(src, a, res, k, i + 1); // recursively call generate function.
        }
    }
}

void permute(string str, string out, vector<string>& des) {
    if (str.size() == 0) { // if string is clean , push an permulate to vector string
        des.push_back(out);
        return;
    }
    for (int i = 0; i < str.size(); i++) {
        permute(str.substr(1), out + str[0], des); // recursively call permute to change position of letter
        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;
}

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

void removeDuplicate(vector<string>& src) {
    for (int i = src.size() - 1; i > 0; i--) { // check from the last to the end of duplicate then remove the last, hold the first.
        if (checkIfExist(src, src[i], i))
            src.erase(src.begin() + i);
    }
}

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<string> ans;
    for (int i = 3; i <= letter.size(); i++)
    {
        int* a = new int[i + 1]; // init an array to hold positon of element 
        memset(a, 0, i + 1); // set all element to 0
        char* c = new char[i + 1];
        generate(letter, a, c, i, 1);
        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();
        delete[]c;
        delete[]a;
    }
    sort(ans.begin(), ans.end());
    removeDuplicate(ans);
    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