【题意】给你m个单词的词典和一句话，这句话中的每个单词都来自字典，字典中的每一个单词重复可用，把这句话所有大写字母变成小写字母，然后反转单词去掉空格，要求你恢复这句话。

【解题方法】Trie+dp.dp[i]=:以i结尾的字符串是否可以解密，为记录答案直接存长度就可以了。复杂度O(n*1000)

【AC 代码】

//zxy
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int maxm=1e6+10;
int n,m,dp[maxn];
string s,t[maxn];
struct Trie{
    int rt,sz;
    int nex[maxm][26],id[maxm];
    int newnode(){
        id[sz]=-1;
        memset(nex[sz],-1,sizeof(nex[sz]));
        return sz++;
    }
    void init(){
        sz=0;
        rt=newnode();
    }
    void insert(string &s,int x){
        int u=rt;
        for(int i=(int)s.size()-1; ~i; i--){
            int c=tolower(s[i])-'a';
            int &v=nex[u][c];
            if(v==-1) v=newnode();
            u=v;
        }
        id[u]=x;
    }
    void query(int idx){
        int u=rt;
        for(int i=idx; i<(int)s.size(); i++){
            u=nex[u][s[i]-'a'];
            if(u==-1) return ;
            if(~id[u]&&!dp[i+1]) dp[i+1]=id[u];
        }
    }
}trie;

int main()
{
    cin>>n>>s>>m;
    trie.init();
    for(int i=1; i<=m; i++){
        cin>>t[i];
        trie.insert(t[i],i);
    }
    dp[0]=1;
    for(int i=0; i<n; i++){
        if(!dp[i]) continue;
        trie.query(i);
    }
    vector<int>ans;
    int u=n;
    while(u){
        ans.push_back(dp[u]);
        u-=t[dp[u]].size();
    }
    for(int i=ans.size()-1; ~i; i--){
        cout<<t[ans[i]]<<" ";
    }
    cout<<endl;
}