Spy Syndrome 2

题意：
描述了一种加密技术，现在将加密后的字符串和字典给出，要你求还原后的字符串。
加密方式：
①将所有字母改为小写字母
②将所单词翻转
③将所有空格去掉

思路：
你可以将字典中的单词按翻转后的结果插入字典树中。
然后dfs加密后的字符串从字典树中查找满足的可划分的单词。

代码：

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

typedef long long ll;
const ll inf=1e9+7;
const int N=105;

int n, m, tree[1000005][26], flag[1000005], pos=1, jie[1000005], ji=0;
string s, t[100005], ti;

void build(int i)
{
    int now=0;
    for(int i=0;i<ti.length();i++)
    {
        int w=ti[i]-'a';
        if(tree[now][w]==0)
        {
            tree[now][w]=pos++;
        }
        now=tree[now][w];
    }
    flag[now]=i;
}

int dfs(int i)
{
    if(i>=s.length())
    {
        return 1;
    }
    int now=0;
    while(i<s.length())
    {
        int w=s[i]-'a';
        if(tree[now][w]==0)
        {
            break;
        }
        now=tree[now][w];
        i++;
        if(flag[now]!=0)
        {
            if(dfs(i))
            {
                jie[ji++]=flag[now];
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    scanf("%d",&n);
    cin >> s;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        cin >> t[i];
        ti=t[i];
        reverse(ti.begin(),ti.end());
        for(int j=0;j<ti.length();j++)
        {
            if(ti[j]<'a')
            {
                ti[j]+=32;
            }
        }
        build(i);
    }
    dfs(0);
    for(int i=ji-1;i>=0;i--)
    {
        cout << t[jie[i]];
        printf("%c",i==0?'\n':' ');
    }
    return 0;
}