公式解説と似た方法ですが、包除原理を用いて解きます。

集合 \(T_i\) を、「長さ \(L\) の英小文字からなる文字列のうち、連続部分列として \(S_i\) を含まないもの全体の集合」とします。

集合 \(U\) を、「長さ \(L\) の英小文字からなる文字列全体の集合」とします。

求めたいものは「連続部分列として \(S_i\) を含まないような \(i\) が存在しないもの」の個数なので、次のようになります。

\[|U|-|T_1\cup T_2\cup \cdots\cup T_N|\]

これは、包除原理より、次と等しいです。

\[\sum_{F\subset\{1,2,\cdots, N\}} (-1)^{|F|} \left| \bigcap_{i\in F} T_i \right|\]

ただし \(F=\emptyset\) のとき \(\bigcap_{i\in F} T_i = U\) とします。

\(\left| \bigcap_{i\in F} T_i \right|\) とは、「\(i\in F\) なら、連続部分列として \(S_i\) を含まない」（\(i\not \in F\) なら連続部分列として \(S_i\) を含んでも含まなくてもよい）ような長さ \(L\) の英小文字からなる文字列の個数です。

\(F\) の部分集合を \(1\) つ決めたとき、公式解説と同じような DP を行って \(\left| \bigcap_{i\in F} T_i \right|\) を求めます。 \(\mathrm{dp}[i][last]\) を、文字列の \(i\) 文字目まで決めたとき、文字列の末尾が \(last\) であるようなものとします。ただし、\(last\) は \(i\in F\) における \(S_i\) の prefix であるようなものしかとらなくてよく、\(last\) が \(S_i (i \in F)\) となるような遷移は禁止します。

このDPは、 \(M = \left|\sum_{i=1}^N S_i \right|, \sigma = 26\) として \(O(LM\sigma)\) 時間で計算できます。

そして、 \(F\) の部分集合は \(2^N\) 通りあるので、この問題に \(O(2^N LM \sigma)\) 時間で答えることができます。空間計算量は \(O(LM\sigma)\) あるいは \(O(M\sigma)\) です。