fork download 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <unordered_map>
  4. #include <vector>
  5. #include <string>
  6. #include <sstream>
  7. #include <algorithm>
  8. #include <queue>
  9.  
  10. using namespace std;
  11.  
  12. struct TrieNode {
  13.     unordered_map<char, TrieNode*> children;
  14.     bool isEndOfWord;
  15.     int frequency;
  16.  
  17.     TrieNode() : isEndOfWord(false), frequency(0) {}
  18. };
  19.  
  20. class Trie {
  21. private:
  22.     TrieNode* root;
  23.  
  24.     void getSuggestionsHelper(TrieNode* node, string prefix, vector<pair<string, int>>& results) {
  25.         if (node->isEndOfWord)
  26.             results.push_back({prefix, node->frequency});
  27.  
  28.         for (auto& pair : node->children) {
  29.             getSuggestionsHelper(pair.second, prefix + pair.first, results);
  30.         }
  31.     }
  32.  
  33. public:
  34.     Trie() { root = new TrieNode(); }
  35.  
  36.     void insert(const string& word) {
  37.         TrieNode* current = root;
  38.         for (char ch : word) {
  39.             ch = tolower(ch);
  40.             if (!isalpha(ch)) continue;
  41.             if (!current->children[ch]) current->children[ch] = new TrieNode();
  42.             current = current->children[ch];
  43.         }
  44.         current->isEndOfWord = true;
  45.         current->frequency++;
  46.     }
  47.  
  48.     bool search(const string& word) {
  49.         TrieNode* current = root;
  50.         for (char ch : word) {
  51.             ch = tolower(ch);
  52.             if (!isalpha(ch)) continue;
  53.             if (!current->children[ch]) return false;
  54.             current = current->children[ch];
  55.         }
  56.         return current->isEndOfWord;
  57.     }
  58.  
  59.     vector<pair<string, int>> getSuggestions(const string& prefix) {
  60.         TrieNode* current = root;
  61.         for (char ch : prefix) {
  62.             ch = tolower(ch);
  63.             if (!isalpha(ch)) continue;
  64.             if (!current->children[ch]) return {};
  65.             current = current->children[ch];
  66.         }
  67.  
  68.         vector<pair<string, int>> results;
  69.         getSuggestionsHelper(current, prefix, results);
  70.         sort(results.begin(), results.end(), [](auto& a, auto& b) {
  71.             return b.second < a.second;
  72.         });
  73.         return results;
  74.     }
  75.  
  76.     void save(ofstream& out, TrieNode* node, string path = "") {
  77.         if (node->isEndOfWord)
  78.             out << path << " " << node->frequency << endl;
  79.  
  80.         for (auto& p : node->children) {
  81.             save(out, p.second, path + p.first);
  82.         }
  83.     }
  84.  
  85.     void saveToFile(const string& filename) {
  86.         ofstream out(filename);
  87.         if (out.is_open()) {
  88.             save(out, root);
  89.             out.close();
  90.         }
  91.     }
  92.  
  93.     void loadFromFile(const string& filename) {
  94.         ifstream in(filename);
  95.         string word;
  96.         int freq;
  97.         while (in >> word >> freq) {
  98.             TrieNode* current = root;
  99.             for (char ch : word) {
  100.                 if (!current->children[ch]) current->children[ch] = new TrieNode();
  101.                 current = current->children[ch];
  102.             }
  103.             current->isEndOfWord = true;
  104.             current->frequency = freq;
  105.         }
  106.         in.close();
  107.     }
  108. };
  109.  
  110. // ---------------------------
  111. // Ung dung 1: Kiem tra chinh ta
  112. void spellChecker(Trie& trie) {
  113.     ifstream dictFile("words.txt");
  114.     if (!dictFile.is_open()) {
  115.         cout << "Khong the mo file words.txt\n";
  116.         return;
  117.     }
  118.  
  119.     string word;
  120.     while (dictFile >> word) {
  121.         trie.insert(word);
  122.     }
  123.     dictFile.close();
  124.  
  125.     cout << "Nhap ten file van ban can kiem tra: ";
  126.     string textPath;
  127.     getline(cin, textPath);
  128.     ifstream textFile(textPath);
  129.     if (!textFile.is_open()) {
  130.         cout << "Khong the mo file van ban!\n";
  131.         return;
  132.     }
  133.  
  134.     ofstream outFile("misspelled.txt");
  135.     string line;
  136.     while (getline(textFile, line)) {
  137.         stringstream ss(line);
  138.         while (ss >> word) {
  139.             word.erase(remove_if(word.begin(), word.end(), [](char ch) {
  140.                 return !isalpha(ch);
  141.             }), word.end());
  142.  
  143.             if (!trie.search(word)) {
  144.                 cout << "Sai chinh ta: " << word << endl;
  145.                 outFile << word << endl;
  146.             }
  147.         }
  148.     }
  149.  
  150.     textFile.close();
  151.     outFile.close();
  152. }
  153.  
  154. // ---------------------------
  155. // Ung dung 2: Goi y hoan thien tu
  156. void autocomplete(Trie& trie) {
  157.  
  158.     cout << "Nhap ten file chua du lieu nguoi dung: ";
  159.     string inputFile;
  160.     getline(cin, inputFile);
  161.  
  162.     ifstream in(inputFile);
  163.     string word;
  164.     while (in >> word) {
  165.         trie.insert(word);
  166.     }
  167.     in.close();
  168.  
  169.     string prefix;
  170.     cout << "Nhap tien to can goi y (>= 2 ky tu, go 'exit' de thoat): ";
  171.     while (cin >> prefix) {
  172.         if (prefix == "exit") break;
  173.         if (prefix.size() < 2) {
  174.             cout << "Vui long nhap it nhat 2 ky tu.\n";
  175.             continue;
  176.         }
  177.         auto suggestions = trie.getSuggestions(prefix);
  178.         if (suggestions.empty()) {
  179.             cout << "Khong tim thay goi y.\n";
  180.         } else {
  181.             cout << "Goi y:\n";
  182.             for (auto& [w, freq] : suggestions)
  183.                 cout << w << " (" << freq << ")\n";
  184.         }
  185.         cout << "\nNhap tiep hoac go 'exit' de thoat: ";
  186.     }
  187.  
  188.     trie.saveToFile("user_trie.txt");
  189.     cout << "Da luu lai cay prefix.\n";
  190. }
  191.  
  192. // ---------------------------
  193. // Chuong trinh chinh
  194. int main() {
  195.     Trie trie;
  196.     int choice;
  197.  
  198.     cout << "==== CHUONG TRINH CAY PREFIX (TRIE) ====\n";
  199.     cout << "1. Kiem tra chinh ta\n";
  200.     cout << "2. Goi y hoan thien tu\n";
  201.     cout << "3. Thoat\n";
  202.     cout << "========================================\n";
  203.     cout << "Nhap lua chon: ";
  204.     cin >> choice;
  205.     cin.ignore();
  206.  
  207.     if (choice == 1) {
  208.         spellChecker(trie);
  209.     } else if (choice == 2) {
  210.         autocomplete(trie);
  211.     } else {
  212.         cout << "Thoat chuong trinh.\n";
  213.     }
  214.  
  215.     return 0;
  216. }
  217.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
==== CHUONG TRINH CAY PREFIX (TRIE) ====
1. Kiem tra chinh ta
2. Goi y hoan thien tu
3. Thoat
========================================
Nhap lua chon: Thoat chuong trinh.
https://ideone.com/gasCGA
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!