题解

思路

任意一次 $s_i+s_j$ 的出现都存在唯一的拼接分割点：$s_i$ 在该点左侧结束，$s_j$ 从该点右侧开始。因此可以按分割点计数，而不必真的枚举所有 $n^2$ 个拼接串。

做法

子任务 1：枚举有序对

在 $n\le 20$、$|t|\le 60$ 时，枚举每个有序对 $(i,j)$，构造 $s_i+s_j$，再在 $t$ 中直接查找所有允许重叠的出现。把所有出现次数相加即可。

这一做法直接对应定义，时间复杂度约为 $O(n^2|t|\max |s_i|)$。

子任务 2：正反 AC 自动机

建立包含所有 $s_i$ 的 AC 自动机。每个结点记录以它结尾的模式串编号数；重复字符串要重复计数。建立失配指针后，把失配祖先的结尾数累加到当前结点。用文本 $t$ 在自动机上运行，得到 $L_k$：在位置 $k$ 结尾的模式串总数。

再把所有模式串和文本都反转，重复同样过程。反转文本中某个位置的“结尾模式数”，映射回原文本后就是 $R_k$：在位置 $k$ 开始的模式串总数。

枚举原文本相邻字符之间的分割点。若左侧最后一个位置为 $k$，则可选择的左模式有 $L_k$ 个，可选择的右模式有 $R_{k+1}$ 个，贡献为 $L_kR_{k+1}$。答案为

正确性说明

AC 自动机在位置 $k$ 的状态表示文本前缀的最长 Trie 后缀。沿失配指针累加终止标记后，该状态的权值恰好等于所有在 $k$ 处结尾的模式串编号数，所以正向扫描得到的 $L_k$ 正确。反转字符串把“在原串某处开始”一一变成“在反转串对应位置结束”，因此 $R_k$ 也正确。

每次 $s_i+s_j$ 的出现有唯一拼接边界，并且会在对应分割点的乘积 $L_kR_{k+1}$ 中被计数一次；反过来，乘积中选择的任意一对模式串确实在该边界两侧连续出现，形成一次拼接串出现。因此求和与题目要求一一对应。

复杂度分析

令 $S=\sum |s_i|$。建立两个自动机并扫描文本的时间复杂度为 $O(26S+|t|)$，空间复杂度为 $O(26S+|t|)$。