fork download
copy 
  1. /*
  2. Given a list of words, write a program to find the longest word made of other words in the list.
  3.  
  4. find the longest compound word in the list that is constructed by concatenating the words 
  5. in the list. the compound word also needs to exist in the list of words.
  6.  
  7. the algorithm will be used for 300k words!
  8. the words are lexicographical sorted in the file
  9.  
  10. EXAMPLE
  11. Input: banana, cat, dog, dogwalker, nana, walk, walker
  12. Output: dogwalker
  13. */
  14.  
  15. #include <iostream>
  16. #include <string>
  17. #include <vector>
  18. #include <chrono>
  19. #include <fstream>
  20. #include <unordered_set>
  21. using namespace std;
  22.  
  23. class LCW {
  24.   private:
  25.     vector<string> words;
  26.     unordered_set<string> words_ht;
  27.  
  28.   private:
  29.     bool is_compound_word(string candidate, int &count) {
  30.         vector<string> prefixes;
  31.         generate_prefix(candidate, prefixes);
  32.         bool found = false;
  33.  
  34.         for (auto prefix = prefixes.begin(); prefix != prefixes.end(); prefix++) {
  35.             count++;
  36.             auto suffix = candidate.substr(prefix->size(), candidate.size() - prefix->size());
  37.  
  38.             if (suffix.size() == 0 && count > 1) {
  39.                 return true;
  40.             } else {
  41.                 auto found = is_compound_word(suffix, count);
  42.                 if (found) {
  43.                     return true;
  44.                 }
  45.             }
  46.         }
  47.  
  48.         count--;
  49.         return found;
  50.     }
  51.  
  52.     void generate_prefix(string candidate, vector<string> &prefixes) {
  53.         for (auto i = 2; i <= candidate.size(); i++) {
  54.             auto prefix = candidate.substr(0, i);
  55.  
  56.             auto it = words_ht.find(prefix);
  57.             if (it != words_ht.end()) {
  58.                 prefixes.push_back(prefix);
  59.             }
  60.         }
  61.     }
  62.  
  63.   public:
  64.     bool load_words(string filename) {
  65.         //string tmp;
  66.  
  67.         //while (cin>>tmp) {
  68.         //  t.insert(tmp);
  69.         //  words.push_back(tmp);
  70.         //}
  71.  
  72.         std::ifstream file;
  73.         file.open(filename.c_str(), std::ios::in);
  74.         if (!file.is_open()) {
  75.             return false;
  76.         }
  77.  
  78.         std::string line;
  79.  
  80.         while (getline(file, line)) {
  81.             words.push_back(line);
  82.             words_ht.insert(line);
  83.         }
  84.  
  85.         cout << words.size() << endl;
  86.  
  87.         return true;
  88.     }
  89.  
  90.     string get_result() {
  91.         string longest_word;
  92.         int count;
  93.  
  94.         for (auto word: words) {
  95.             count = 0;
  96.  
  97. 			if (word.size() < longest_word.size()) {
  98. 				continue;
  99. 			}
  100.  
  101.             if (is_compound_word(word, count)) {
  102.                 if (word.size() > longest_word.size()) {
  103.                     longest_word = word;
  104.                 }
  105.             }
  106.         }
  107.  
  108.         return longest_word;
  109.     }
  110. };
  111.  
  112. int main() {
  113.     // your code goes here
  114.  
  115.     auto start = chrono::steady_clock::now();
  116.  
  117.     LCW lcw;
  118.     bool file_found = lcw.load_words("words.txt");
  119.     if (!file_found) {
  120.     	cerr << "file not found" << endl;
  121.     	return 0;
  122.     }
  123.  
  124.     string longest_comp_word = lcw.get_result();
  125.  
  126.     auto end = chrono::steady_clock::now();
  127.     auto diff = end - start;
  128.     cout << chrono::duration <double, milli> (diff).count() << " ms" << endl;
  129.  
  130.     cout << longest_comp_word << endl;
  131.  
  132.     return 0;
  133. }
Success #stdin #stdout #stderr 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
file not found
https://ideone.com/WLZMOI
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!