用words数组建立trie树，再用words中的词在trie树中做dfs。
dfs过程中如果碰到存在的单词(cnt[son[p][u]] > 0)，则p指针重新跳转到root，继续往后匹配。

//https://leetcode.com/problems/concatenated-words/
const int N = 50000;
class Solution {
public:
    vector<string> ans;
    int son[N][26], cnt[N], idx;
    void insert(string s){
        int p = 0;
        for (auto c : s){
            int u = c - 'a';
            if (!son[p][u]) son[p][u] = ++idx;
            p = son[p][u];
        }
        cnt[p]++;
    }

    bool dfs(string& s, int i_s, int p, int w){
        if (i_s == s.length()){
            if (w > 1)  {
                ans.push_back(s);   
                return true;
            }
            else
                return false;
        }

        for (int i=i_s; i<s.length(); i++){
            int u = s[i]-'a';
            int v = son[p][u];
            if (!v) return false;//匹配失败
            if (cnt[v])     
                //从头dfs
                if (dfs(s, i+1, 0, w + 1)) return true; 
            p = son[p][u];
        }
        return false;
    }

    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        //init
        idx = 0;
        memset(son, 0, sizeof son); memset(cnt, 0, sizeof cnt);

        for (auto s : words)    insert(s);
        for (auto s : words)    dfs(s, 0, 0, 0);
        return ans;
    }
};