struct PrefixTree{
    unique_ptr<PrefixTree> children[26];
    bool isEnd;
    PrefixTree(): isEnd(false){}
    bool isConcat(const string &w, int pos, char *isConcatCache){
        auto begin = w.begin() + pos, end = w.end();
        if(begin == end){
            return true;
        }
        if(pos > 990){
            cout<<pos<<endl;
        }
        if(isConcatCache[pos]){
            return isConcatCache[pos] == 2;
        }
        auto curr = this;
        while(begin != end){
            auto nextc = *begin - 'a';
            if(curr->children[nextc]){
                curr = curr->children[nextc].get();
                ++begin;
                if(curr->isEnd){
                    if(isConcat(w, begin - w.begin(), isConcatCache)){
                        isConcatCache[pos] = 2;
                        return true;
                    }
                }
            }else{
                break;
            }
        }
        isConcatCache[pos] = 1;
        return false;
    }
    void insert(string &word){
        auto curr = this;
        auto begin = word.begin(), end = word.end();
        while(begin != end){
            auto nextc = *begin - 'a';
            if(!curr->children[nextc]){
                curr->children[nextc] = make_unique<PrefixTree>();
            }
            curr = curr->children[nextc].get();
            ++begin;
        }
        curr->isEnd = true;
    }
};

struct ReleasePrint{
    ~ReleasePrint(){
        cout<<"Releasing"<<endl;
    }
};

class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        ReleasePrint r;
        if(words.empty()){
            return vector<string>();
        }
        sort(words.begin(), words.end(), [](auto x, auto y){return x.size() < y.size();});
        int maxsize = words.back().size() + 1;
        //cout<<"maxsize: "<<maxsize<<endl;
        vector<string> result;
        {
            unique_ptr<char[]> cache = make_unique<char[]>(maxsize);
            PrefixTree tree;
            for(auto &w: words){
                if(w.empty()){
                    continue;
                }
                memset(cache.get(), 0, sizeof(char) * maxsize);
                if(tree.isConcat(w, 0, cache.get())){
                    result.emplace_back(w);
                }else{
                    //cout<<"Insert "<<w<<endl;
                    tree.insert(w);
                }
            }
        }
        cout<<"returning"<<endl;
        return std::move(result);
    }
};