牛客第二场多校A题All with Pairs: 建完AC自动机dfs一遍即可

All with Pairs

https://ac.nowcoder.com/acm/contest/5667/A

牛客第二场多校A题All with Pairs: 建完AC自动机dfs一遍即可

链接
传送门: here
题意 $n(1e5),\sum |s_i| \le 1e6$
求 $\sum_{i=1}^n\sum_{j=1}^nf(si,sj)\;mod\;998244353$
$f(s, t)$ as the maximum $i$ that satisfy $s_{1\dots i} = t_{|t|-i+1 \dots |t|}$

思路
为字符串 $u$ 找其他字符串的前缀和 $u$ 的后缀所产生的贡献。每个节点保存字典树子树中 $end\;node$ 信息。遍历 $fail$ 连接树，前面遍历过的节点都是我的后缀为每个字符串记录一下遍历到当前节点匹配的最长前缀即可。回溯时记得还原。

备注

AC_CODE
看我的提交即可，四斋蒸鹅心。