题解

思路

每次合并只需要知道当前结果的后缀与下一个单词前缀的最长公共部分。不同子任务分别可以直接处理单字符、逐个尝试重叠长度，或用 KMP 在线性时间内求出最长重叠。

做法

子任务一：单字符单词

每个新单词只有一个字符。若它与当前结果的末字符相同，最长重叠长度为 $1$，无需追加；否则重叠长度为 $0$，直接追加该字符。依次处理全部单词即可。

子任务二：枚举重叠长度

设当前结果为 $a$，下一个单词为 $b$。从 $\min(|a|,|b|)$ 开始向下枚举重叠长度 $k$，逐字符检查 $a$ 的长度为 $k$ 的后缀是否等于 $b$ 的长度为 $k$ 的前缀。找到第一个合法的 $k$ 后，追加 $b$ 从位置 $k$ 开始的部分。

总长度不超过 $3000$ 时，这种朴素比较足以通过。

满分算法

仍然设当前结果为 $a$，下一个单词为 $b$。只有 $a$ 的最后 $\min(|a|,|b|)$ 个字符可能参与重叠，记这段后缀为 $c$。

构造字符串

其中分隔符 # 不会出现在输入中。计算该字符串的 KMP 前缀函数。最后一个位置的前缀函数值，正好是既为 $b$ 的前缀、又为 $c$ 的后缀的最长字符串长度，也就是本次合并的最长重叠长度。随后只需把 $b$ 未重叠的部分追加到答案。

每次参与计算的 $c$ 长度不超过 $|b|$，因此所有 KMP 字符串的总长度与输入总长度同阶。

复杂度

单字符子任务的时间复杂度为 $O(n)$。朴素算法的最坏时间复杂度为 $O(S^2)$，其中 $S$ 为所有输入单词的总长度。

满分算法的时间复杂度为 $O(S)$，空间复杂度为 $O(S)$。

正确性说明

对一次合并，KMP 前缀函数末值表示构造串的最长真前后缀长度。由于分隔符只出现一次，任何跨过分隔符的更长匹配都不可能成立；因此该前后缀必然同时是 $b$ 的前缀和 $c$ 的后缀。反过来，任何合法重叠都是 $b$ 的前缀与 $c$ 的后缀，也对应构造串的一个前后缀。故前缀函数末值恰为最长重叠长度。

每一步都保留当前结果与下一个单词的最长合法重叠，并追加其余字符，正是题目规定的合并操作。按输入顺序归纳，最终字符串即为全部单词依次合并后的结果。