你好！作为一名教练，我很高兴能为你解析这道经典的字符串处理题目。这道题在 NOI 竞赛中属于字符串基础进阶题，考查的是对匹配算法的灵活运用。

一、 预备知识点

在挑战这道题之前，你需要掌握以下核心知识：

1. 字符串哈希 (String Hashing)：能够 $O(1)$ 时间内比较两个子串是否相等。
2. KMP 算法 (Knuth-Morris-Pratt)：理解 next 数组（或 fail 指针）的含义——即“最长相等前后缀”。
3. 贪心思想：理解为什么每次只需要找“当前能匹配的最长部分”。
4. 内存管理：处理总长度达 $10^6$ 的字符串拼接。

二、 题目描述 (NOI 风格)

题目名称：Compress Words 时间限制：1.0s 内存限制：256MB

【问题描述】 给你 $n$ 个单词。你需要按照给定的顺序将它们合并成一个连续的句子。合并规则如下： 对于当前已合并的字符串 $S$ 和下一个待合并的单词 $T$，你需要找到一个最长的字符串 $X$，使得 $X$ 既是 $S$ 的后缀，又是 $T$ 的前缀。在合并时，保留 $S$，并在其后接上 $T$ 去掉前缀 $X$ 后剩余的部分。

【输入格式】 第一行包含一个整数 $n$，表示单词的数量。 第二行包含 $n$ 个由大写字母、小写字母或数字组成的单词，单词之间用空格隔开。

【输出格式】 输出一行，表示最终合并完成的字符串。

【样例输入】

5
sample please ease in out

【样例输出】

sampleaseinout

【数据范围说明】

• $1 \le n \le 10^5$
• 所有单词的总长度不超过 $10^6$。
• 单词仅包含 'a'-'z', 'A'-'Z', '0'-'9'。

三、 教学启发与思路引导 (草稿纸推演)

请拿出你的草稿纸，跟我一起画图：

第一步：理解核心矛盾

假设合并后的字符串为 res，现在要合并新单词 cur。 我们需要找到 L，使得 res.suffix(L) == cur.prefix(L)，且 L 越大越好。 限制条件：L 不能超过 res 的长度，也不能超过 cur 的长度。 思考：难道我们要从 L = min(|res|, |cur|) 开始一个一个字符暴力比对吗？ 结论：总长度 $10^6$，暴力 $O(N^2)$ 必 TLE。

第二步：抽象模型

在草稿纸上画两个条：

res: [ ... a b c d ]  (取最后一部分)
cur: [ a b c d ... ]  (取开头一部分)

这像不像 KMP 里的 next 数组定义？next[i] 表示前 $i$ 个字符组成的子串中，最长的相等前后缀。

第三步：算法选择

方法 A：KMP 思想 我们可以构建一个临时字符串：cur + '#' + res.suffix(min(|res|, |cur|))。 对这个临时字符串求一次 next 数组。最后一位的 next 值就是我们要找的 L。 注意：为了空间效率，我们不需要真的切出 res 的后缀，只需在原数组上操作。

方法 B：字符串哈希

1. 预计算 cur 的前缀哈希。
2. 动态维护 res 的后缀哈希。
3. 枚举 L 从 min(|res|, |cur|) 到 $1$，第一个满足 Hash(res_suffix) == Hash(cur_prefix) 的就是答案。

第四步：复杂度优化思考

• 时间：合并 $n$ 个词，总长度 $L_{total}$。如果每次只处理 min(|res|, |cur|) 的长度，KMP 或哈希的总复杂度均为 $O(L_{total})$。
• 空间：直接在 std::string 或字符数组上追加，避免频繁申请内存。

四、 算法流程图 (伪代码提示)

graph TD
    A("开始: 读取 n") --> B("初始化 res 为第一个单词")
    B --> C{"枚举 i 从 2 到 n"}
    C -- "是" --> D("读取当前单词 cur")
    D --> E("计算待匹配长度 len = min(res.length, cur.length)")
    E --> F("构建匹配串: cur.substr(0, len) + '#' + res.suffix(len)")
    F --> G("运行 KMP getNext 或 计算 Hash")
    G --> H("找到最大重叠长度 L")
    H --> I("将 cur.substr(L) 追加到 res 末尾")
    I --> C
    C -- "否" --> J("输出 res")
    J --> K("结束")

    style F fill:#f9f,stroke:#333,stroke-width:2px
    style G fill:#bbf,stroke:#333,stroke-width:2px

五、 关键词理解 (读题技巧)

在读这类字符串题目时，看到以下关键词要立即反应：

1. "最长前缀等于后缀"：这是 KMP 算法或 Z 算法（扩展KMP）的标志性描述。
2. "依次合并"：暗示我们要维护一个当前的增量结果，而不是全局同时处理。
3. "总长度 $10^6$"：提示算法必须是线性 $O(N)$ 或 $O(N \log N)$，排除所有 $O(N^2)$ 的暴力。
4. "无重复叠加"：字符串重叠覆盖问题，典型的贪心。

六、 竞赛避坑指南 (NOI 注意事项)

1. 哈希冲突：如果你选择哈希法，请务必使用 双哈希（Double Hash）或者 大质数模数（如 $10^9+7$ 和 $10^9+9$ 组合，或 $2^{61}-1$）。单哈希在 Codeforces 或 NOI 强数据下极易被卡。
2. 内存限制：不要在循环里频繁 res += cur.substr(...)。在 C++ 中，substr 会产生临时字符串，频繁操作可能导致内存碎片或效率低下。建议记录下标直接追加。
3. KMP 边界：在 KMP 做法中，中间的连接符（如 #）必须是不会在单词中出现的字符，否则会干扰匹配。

通过以上引导，你应该可以开始尝试编写代码了。记住，先在纸上模拟一遍 sample 和 please 的合并过程，确定你的 L 是如何算出来的！加油！