#include <iostream> #include <string> #include <vector> // Used to handle vector #include <fstream> // Used to read file from the disk #include <cassert> // Used to assert #include <unordered_set> // Used to handle set #include <sys/time.h> using namespace std; class Solution { public: vector<string> findAllMatches(vector<string> &words) { if (words.size() <= 2) return {}; vector<string> res; // A array used to store all the expected word unordered_set<string> dict(words.begin(), words.end()); // A set used to store all unique word int i = 0; for (string s : words) { // Filter the words from the vector `words` int len = s.size(); // Get it's size if (len == 0) continue; int flags[len + 1]; // A array used to store intermediates flags[0] = true; for (int i = 1; i <= len; ++i) { // Initialize `flags` flags[i] = false; } for (int i = 0; i < len; ++i) { if (!flags[i]) continue; for (int j = i + 1; j <= len; ++j) { int t = j - i; if (t < len && dict.count(s.substr(i, t))) { flags[j] = true; } } } // If the last element of the `flags` is true then append it to the res if (flags[len]) res.push_back(s); } return res; // Return final result res } }; vector<string> readTxt(string file) { // Read lines of the given file to vector ifstream infile; // A ifstream instance infile.open(file.data()); // Connect file stream object to the file assert(infile.is_open()); // If failed to open file then output error messages and prevent the program from continuing to run vector<string> words; string word; // Read each line from the file for loop while (getline(infile, word)) { word = word.substr(0, word.size() - 1); // Remove '\n' in the tail of the line if (word != "") { // If the word is not blank words.push_back(word); } } infile.close(); // Close file input stream return words; } int main(int args, char **argv) { struct timeval tv; if (args < 2) { // The file path must be provided! cout << "The word file is missing:(!" << endl; } Solution *s = new Solution; vector<string> words = readTxt(argv[1]); // Read all lines from the file to a vector with string type gettimeofday(&tv, NULL); // Begin to calculate... int begin = tv.tv_sec * 1000000 + tv.tv_usec; vector<string> res = s->findAllMatches(words); delete s; gettimeofday(&tv, NULL); // Done! int end = tv.tv_sec * 1000000 + tv.tv_usec; string second = ""; // The 2nd longest word string max = ""; // The 1st longest word for (string word : res) { // Loop through the result if (word.size() > max.size()) { // If the word's length > current longest string's length second = max; max = word; } else if (word.size() > second.size()) { // If the word's length > current 2nd longest string's length second = word; } } // Print result cout << "The number of lines: " << words.size() << endl; cout << "The 1st longest: " << max << endl; cout << "The 2nd longest: " << second << endl; cout << "All concatenated words count: " << res.size() << endl; cout << "spend " << (end - begin) / 1000000.0 << "s to run the core algorithm." << endl; return 0; }