题目链接

Codeforces Luogu

题意

给定两个字符串s、t，求s的非空前缀后接上t的非空前缀形成的本质不同字符串种类数

思路

神仙思维题。 设一组本质相同的答案串为 AB ，且 A, B 分别为 s, t 的非空前缀。我们在这堆本质相同的串里，选出 A 最短、B 最长的一种（记为 A'B' ）代表这一类。那么答案就是所有串的个数减去重复的。设 A''B'' 与 A'B' 重复，那它应该是长这样的： 上图颜色相同的线段代表字串相同。 容易看出 B'' 是 B' 的 Border（既是前缀又是后缀），并且 B' 去掉 B'' 这一段在 A 中出现过（绿色的两段）。可以 kmp/exkmp 求出 t 的前缀的 Border 和 t 的每个前缀在 s 中出现的次数。 但是还有个问题。如果我们枚举 t 的每个前缀，再枚举它的每一个 Border，该怎么确定它是 A 最短、B 最长的呢？ 我们考虑对于 t 的每一个前缀，只减去它的最长 Border 的贡献。这样，如果有更长的 B 仍能与另一个 A 构成这个串，这个新 B 就会减去原来的贡献。而最长的前缀 B' 的贡献是唯一的不会被减去的那个。 代码就不放了。