题目链接：Codeforces 633C

Yash 研究出了一种新的密码技术。对于给定的句子，密码通过以下方法生成：

1. 将所有字母都变成小写。
2. 将每个单词分别反转。
3. 将句子里的空格全部删除。

现在 Yash 给你一个长度为 $n$ 的加密后的句子 $S$ 和一个长度为 $m$ 的单词列表 $w_i$。请你帮助他找出任何一种可能的原始句子，使得句子里的单词都来自于单词列表。注意：任何给定的单词都可以多次使用。

数据范围：$1 \le \lvert S \rvert \le 10 ^ 4$，$1 \le m \le 10 ^ 5$，$1 \le \lvert w_i \rvert \le 10 ^ 3$，$\sum \lvert w_i \rvert \le 10 ^ 6$。

Solution

我们将所有单词反转后插入到 $\text{Trie}$ 树中，然后用一种类似 $\text{DP}$ 的方法去匹配原串 $S$。如果第 $i$ 个位置能够作为某个单词的结尾，那么我们对其进行标记。考虑当前扫到的位置 $i$，如果 $i - 1$ 被打上了标记，那么从 $i$ 开始尝试匹配。注意一旦匹配成功不能直接退出，必须一直匹配下去！

时间复杂度：$\mathcal O(n \cdot \max \lvert w_i \rvert )$。

Code

#include <iostream>
#include <cctype>
#include <algorithm>

const int N = 1e4 + 5, M = 1e5 + 5;

int n, m, f[N], ans[N];
char s[N];
std::string t[M];

template <int MAX, int S>
struct Trie {
    static const int N = MAX;
    int tot, ch[N][S], end[N];
    void clear(int x) {
        std::fill(ch[x], ch[x] + S, 0);
        end[x] = 0;
    }
    int id(char c) {
        if (isdigit(c)) return c - '0';
        if (isupper(c)) return c - 'A';
        if (islower(c)) return c - 'a';
        return -1;
    }
    void insert(std::string &s, int x) {
        int u = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            int &v = ch[u][id(s[i])];
            if (!v) clear(v = ++tot);
            u = v;
        }
        end[u] = x;
    }
    void query(int x) {
        int u = 0;
        for (int i = x; i <= n; i++) {
            u = ch[u][id(s[i])];
            if (!u) return;
            if (end[u] && !f[i]) f[i] = end[u];
        }
    }
};

Trie<1000005, 26> T;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin >> n >> (s + 1) >> m;
    for (int i = 1; i <= m; i++) {
        std::cin >> t[i];
        std::reverse(t[i].begin(), t[i].end());
        T.insert(t[i], i);
        std::reverse(t[i].begin(), t[i].end());
    }
    f[0] = -1;
    for (int i = 1; i <= n; i++) {
        if (f[i - 1]) T.query(i);
    }
    int tot = 0;
    for (int i = n; i >= 1; i -= (int)t[f[i]].size()) {
        ans[++tot] = f[i];
    }
    for (int i = tot; i >= 1; i--) {
        std::cout << t[ans[i]] << " \n"[i == 1];
    }
    return 0;
}