根据题意，这是一道多模式串多文本串匹配问题。容易想到AC自动机。易知第一行的输入可以用递归/栈的形式模拟并且构建一棵Trie，可以在$\mathrm{O}(|S_0|)$的时间内完成。可以同时构建Fail失配树，时间复杂度$\mathrm{O}(P)$，$P$为Trie的节点总数。
根据题意，这是一道多模式串多文本串匹配问题。容易想到AC自动机。易知第一行的输入可以用递归/栈的形式模拟并且构建一棵Trie，可以在$\mathrm{O}(|S_0|)$的时间内完成。可以同时构建Fail失配树，时间复杂度$\mathrm{O}(P)$，$P$为Trie的节点总数。