/*
Find the longest word which is made of words.
list = test, tester, testertest, testing, testingtester, mytestingtesterprogram, testertestingtesting
output = testertestingtesting
*/
#include "bits/stdc++.h"
using namespace std;
bool isWordMadeOfOtherWords(unordered_set<string>& st, string& word, int index) {
if (index >= word.size()) {
return false;
}
if (index != 0 && (st.find(word.substr(index)) != st.end())) {
return true;
}
bool flag = false;
for (int i=index+1;i<word.size();i++) {
if (st.find(word.substr(index, i-index)) != st.end()) {
if (isWordMadeOfOtherWords(st, word, i)) {
flag = true;
break;
}
}
}
return flag;
}
string longestWordMadeOfOtherWords(vector<string>& wordlist) {
unordered_set<string> st;
for (auto word : wordlist) {
st.insert(word);
}
int maxlen = 0;
string longest_word = "";
for (auto word : wordlist) {
if (maxlen < word.size() && isWordMadeOfOtherWords(st, word, 0)) {
maxlen = word.size();
longest_word = word;
}
}
return longest_word;
}
int main() {
vector<string> wordlist = {"testingtest", "test", "testing", "testtesttest"};
cout << longestWordMadeOfOtherWords(wordlist) << endl;
wordlist = {"test", "tester", "testertest", "testing", "testingtester", "mytestingtesterprogram", "testertestingtesting"};
cout << longestWordMadeOfOtherWords(wordlist) << endl;
}
LyoKCkZpbmQgdGhlIGxvbmdlc3Qgd29yZCB3aGljaCBpcyBtYWRlIG9mIHdvcmRzLgoKbGlzdCA9IHRlc3QsIHRlc3RlciwgdGVzdGVydGVzdCwgdGVzdGluZywgdGVzdGluZ3Rlc3RlciwgbXl0ZXN0aW5ndGVzdGVycHJvZ3JhbSwgdGVzdGVydGVzdGluZ3Rlc3RpbmcKb3V0cHV0ID0gdGVzdGVydGVzdGluZ3Rlc3RpbmcKCiovCgojaW5jbHVkZSAiYml0cy9zdGRjKysuaCIKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpib29sIGlzV29yZE1hZGVPZk90aGVyV29yZHModW5vcmRlcmVkX3NldDxzdHJpbmc+JiBzdCwgc3RyaW5nJiB3b3JkLCBpbnQgaW5kZXgpIHsKCWlmIChpbmRleCA+PSB3b3JkLnNpemUoKSkgewoJCXJldHVybiBmYWxzZTsKCX0KCWlmIChpbmRleCAhPSAwICYmIChzdC5maW5kKHdvcmQuc3Vic3RyKGluZGV4KSkgIT0gc3QuZW5kKCkpKSB7CgkJcmV0dXJuIHRydWU7Cgl9CgoJYm9vbCBmbGFnID0gZmFsc2U7Cglmb3IgKGludCBpPWluZGV4KzE7aTx3b3JkLnNpemUoKTtpKyspIHsKCQlpZiAoc3QuZmluZCh3b3JkLnN1YnN0cihpbmRleCwgaS1pbmRleCkpICE9IHN0LmVuZCgpKSB7CgkJCWlmIChpc1dvcmRNYWRlT2ZPdGhlcldvcmRzKHN0LCB3b3JkLCBpKSkgewoJCQkJZmxhZyA9IHRydWU7CgkJCQlicmVhazsKCQkJfQoJCX0KCX0KCXJldHVybiBmbGFnOwp9CgpzdHJpbmcgbG9uZ2VzdFdvcmRNYWRlT2ZPdGhlcldvcmRzKHZlY3RvcjxzdHJpbmc+JiB3b3JkbGlzdCkgewoJdW5vcmRlcmVkX3NldDxzdHJpbmc+IHN0OwoJZm9yIChhdXRvIHdvcmQgOiB3b3JkbGlzdCkgewoJCXN0Lmluc2VydCh3b3JkKTsKCX0KCglpbnQgbWF4bGVuID0gMDsKCXN0cmluZyBsb25nZXN0X3dvcmQgPSAiIjsKCWZvciAoYXV0byB3b3JkIDogd29yZGxpc3QpIHsKCQlpZiAobWF4bGVuIDwgd29yZC5zaXplKCkgJiYgaXNXb3JkTWFkZU9mT3RoZXJXb3JkcyhzdCwgd29yZCwgMCkpIHsKCQkJbWF4bGVuID0gd29yZC5zaXplKCk7CgkJCWxvbmdlc3Rfd29yZCA9IHdvcmQ7CgkJfQoJfQoJcmV0dXJuIGxvbmdlc3Rfd29yZDsKfQoKaW50IG1haW4oKSB7Cgl2ZWN0b3I8c3RyaW5nPiB3b3JkbGlzdCA9IHsidGVzdGluZ3Rlc3QiLCAidGVzdCIsICJ0ZXN0aW5nIiwgInRlc3R0ZXN0dGVzdCJ9OwoJY291dCA8PCBsb25nZXN0V29yZE1hZGVPZk90aGVyV29yZHMod29yZGxpc3QpIDw8IGVuZGw7CgkKCXdvcmRsaXN0ID0geyJ0ZXN0IiwgInRlc3RlciIsICJ0ZXN0ZXJ0ZXN0IiwgInRlc3RpbmciLCAidGVzdGluZ3Rlc3RlciIsICJteXRlc3Rpbmd0ZXN0ZXJwcm9ncmFtIiwgInRlc3RlcnRlc3Rpbmd0ZXN0aW5nIn07CgoJY291dCA8PCBsb25nZXN0V29yZE1hZGVPZk90aGVyV29yZHMod29yZGxpc3QpIDw8IGVuZGw7Cn0=