题解

思路推导

设最终字符串的长度为 $2N-k$。其中前 $N$ 个字符由 $s$ 固定，后 $N$ 个字符由 $t$ 固定，两部分重叠了 $k$ 个字符。

重叠可行，当且仅当 $s$ 的长度为 $k$ 的后缀等于 $t$ 的长度为 $k$ 的前缀。为了使最终字符串最短，应求最大的可行 $k$，答案为 $2N-k$。

特殊性质

当 $s$ 中所有字符均相同时，任意后缀都只含同一个字符。最大重叠长度就是 $t$ 开头连续出现该字符的数量，可以直接扫描得到。

当 $s$ 中任意两个字符均不同时，若存在非空重叠，其起点字符必须等于 $t$ 的首字符，而这个字符在 $s$ 中至多出现一次。因此只需定位这一个候选起点，并检查对应的后缀和前缀是否相等。

做法

把字符串 t、一个不会出现在小写字母中的分隔符和字符串 s 依次连接，并计算连接串的前缀函数。

最后一个位置的前缀函数值，正好是既为 $t$ 的前缀、又为 $s$ 的后缀的最长字符串长度，即最大重叠长度 $k$。输出 $2N-k$。

正确性证明

若两部分重叠 $k$ 个字符，则同一位置同时属于 $s$ 的后缀与 $t$ 的前缀，所以二者必须相等。反之，若这两个长度为 $k$ 的字符串相等，就可以把它们重合，构造出长度为 $2N-k$ 的合法字符串。

因此，合法字符串与可行重叠长度对应，且长度随 $k$ 增大而减小。前缀函数求得最大的可行 $k$，故所得字符串长度最小。

复杂度分析

一般做法的时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。