本問題は、Trie、Aho-Corasick 法の基本問題です。詳しくは、これらの単語で検索して学習してみてください。

一応ごく簡単に解説を書いておきます。

複数文字列の検索には、Trie がよく用いられます。

Wikipedia：https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%A9%E3%82%A4_(%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)

文字列集合 \(T_1, \ldots, T_N\) に対する Trie を構築し、文字 \(s_1, s_2, \ldots\) にしたがって 走査すると、まず \(T_k = s_1 \ldots s_n\) のように \(S\) の prefix がある \(T_k\) に一致するパターンを見つけることができます。

本問題では、\(S\) の部分文字列 \(s_l\ldots s_r\) が \(T_k\) と一致する状況を見つける必要があります。このためには次が行えればよいです。

• 文字列 \(X\) を用意する。これははじめ空である。
• \(X\) に \(1\) 文字追加する。
• \(X\) のある suffix がある \(T_k\) と一致するならば、そのことを報告する。（本問題では、答に \(1\) を加算し \(X\) を空にする）
• \(X\) を、その suffix のうちで、ある \(T_k\) の prefix となるようなもののうち、最大長のものに置き換える （状態を Trie のノードで表すためにこの操作を行います）

これは、Aho-Corasick 法と呼ばれる方法により実現できます。

Wikipedia：https://ja.wikipedia.org/wiki/%E3%82%A8%E3%82%A4%E3%83%9B%E2%80%93%E3%82%B3%E3%83%A9%E3%82%B7%E3%83%83%E3%82%AF%E6%B3%95

簡単に説明すると、Aho-Corasick 法は、Trie に suffix link / failure link などと呼ばれる辺を追加するものです（BFS 順に計算することでこれが線形時間で行えます）。suffix link の行き先は、Trie の各ノードのうち、それが表す文字列の（自身とは異なるもののうちで）最長 suffix であるようなノードです。

あるノードの suffix が \(T_k\) に一致するか否かは、suffix link を辿って \(T_k\) の表すノードに到達できるかと同値です。よって文字列 \(X\) の表すノードがある \(T_k\) を suffix に持つかという問題は、suffix link の作る木において、根までのパス上に印をつけたノードがあるか否かを判定する問題と定式化できて、全てのノードに対する判定結果を簡単に前計算できます。

「文字列 \(X\) に文字 \(s\) を追加し、ある \(T_k\) の prefix となるようなもののうち、最大長のものに置き換える」という操作を行うためには、「\(s\) が追加できる最大長の suffix」のノードに遷移したあと、\(s\) を追加すればよいです。この遷移先も BFS 順などに計算することで容易に前計算できます。

「コンテスト全体の解説」における公式解説（動画）もこの解法を扱っているようです。