传送门：点击打开链接
题意：原本有一个串有许多单词，中间用空格隔开，后来把单词全部转换成小写，然后翻转，再把中间的所有的空格全部去掉，就得到了一个全是小写字母组成的串。
现在告诉你这样的串，并告诉你字典，要你找出一种满足条件的原串，保证有解。
思路：第一眼感觉有点像AC自动机，，，但是仔细看了下数据范围，10000*1000也只有1000w，加上CF的测评机跑很快，这个复杂度应该是可以接受的，很容易想到trie上暴力搞的方法，注意保存上一个位置，然后就可以利用DFS再倒着输出了。
在插入trie的时候，我们是倒着插入的，然后要把所有的大写转换成小写再插入。
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;const int MX = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;int rear, root;
int Next[MX][26], End[MX];
int New() {rear++;End[rear] = 0;for(int i = 0; i < 26; i++) {Next[rear][i] = -1;}return rear;
}
void Init() {rear = 0;root = New();
}
void Add(char *A, int x) {int n = strlen(A), now = root;for(int i = n - 1; i >= 0; i--) {int id;if('A' <= A[i] && A[i] <= 'Z') id = A[i] - 'A';else id = A[i] - 'a';if(Next[now][id] == -1) {Next[now][id] = New();}now = Next[now][id];}End[now] = x;
}int n, m, last[MX], ans[MX];
char W[MX], temp[MX];
string A[MX];void DFS(int n, bool t = false) {if(last[n]) DFS(last[n]);printf("%s%c", A[ans[n]].c_str(), t ? '\n' : ' ');
}int main() {//FIN;while(~scanf("%d%s%d", &n, W + 1, &m)) {Init(); last[0] = 0;for(int i = 1; i <= m; i++) {scanf("%s", temp);Add(temp, i);A[i] = string(temp);}ans[0] = -1;for(int i = 1; i <= n; i++) {int rt = root;if(!ans[i - 1]) continue;for(int j = i; j <= n; j++) {int id = W[j] - 'a';rt = Next[rt][id];if(rt == -1) break;if(End[rt]) {last[j] = i - 1;ans[j] = End[rt];}}}DFS(n, true);}return 0;
}