容易发现子串有五种形式：\(\empty,\ s,\ s*,\ *t,\ s*t\)，前四种可以建立 suffix automaton 后直接统计，关键在于第五种。
本来想在 \(t\) 处统计答案串，但是发现此时找 \(s\) 就变成了在 fail 树上找，不太能做。所以不妨考虑在 \(s\) 处统计答案串。
考虑原串的 suffix automaton 上的 \(u\) 号节点，其 endpos 集合为 \(\{p_1,p_2,\cdots,p_m\}\)，因为同一个节点上的所有串能匹配的 \(t\) 是相同的，所以只需要考虑以 \(\{p_{1}+2,p_2+2,\cdots, p_m+2\}\) 开头的有多少串即可。
这个问题很好解决：建立反串的 suffix automaton，令以 \(p\) 为开头的后缀在反串的 suffix automaton 上的节点为 \(k_p\)，那么匹配 \(u\) 个串个数就是 \(\{k_{p_{1}+2},k_{p_2+2},\cdots, k_{p_m+2}\}\) 在反串的 suffix automaton 的 fail 树上到根的路径并包含的节点长度总和，说白了就是虚树。
这个东西就用 set 启发式合并就行，注意到一个 \(k_{p}\) 最多合并 \(\log n\) 次，每次合并代价为 \(\log n\)，所以总时间复杂度为 \(O(n\log ^2 n)\) 。
这题主要是 suffix automaton 和 树上链并之类啥的（虚树啥的）的结合，难度我觉得其实到不了 3400 。
代码：Submission #127234490 - Codeforces
【题解】CF1276F Asterisk Substrings
原文：https://www.cnblogs.com/qiulyqwq/p/15196504.html