動的計画法で解きます。

まず、他の文字列 \(S_j\,(j\ne i)\) の部分文字列になっているような文字列 \(S_i\) はないものとして考えます。これにより、文字列を前から決めていったときに2つ以上の文字列が同時に完成することはありません。

このもとで、\(dp[i][t][j]\) を、「\(i\) 文字目でちょうど \(S_j\) が初めて完成していて（\(j=-1\) の時はどれも完成していないものとする）、 \(S_k\,(k\in t)\) を含み \(S_k\,(k\notin t)\) を含まない長さ \(i\) の文字列の個数」とします（\(t\) は \(\{1,2,\dots,N\}\) の部分集合）。

\(S_i\) と \(S_j\) が連続して現れる際、共有できる文字数 \((\ge1)\) としてあり得るものを集合 \(dup_{i,j}\) として前計算して管理しておきます。すると、\(dp[i][t][j]\) は、\(t\) の要素のうち \(S_j\) だけ含まない文字列に \(S_j\) が末尾に来るように文字を足したものの個数から、その過程で新しく \(S_k\) が登場してしまったものの個数をそのうち（初めて登場した \(S_k\) に注目して）引くことで求まるので、
dpの遷移は、

\(dp[i][t][j] = \sum_{k\,\in\,t\,\cup\,\{-1\}}dp[i-|S_j|][t\setminus\{j\}][k]+\sum_{k\,\in\,t\setminus\{j\}}\sum_{m\in dup_{k,j}}dp[i-|S_j|+m][t\setminus\{j\}][k]-\sum_{k\,\notin\,t\setminus\{j\}}\sum_{m\in dup_{k,j}}dp[i-|S_j|+m][(t\setminus\{j\})\cup\{k\}][k]\)

\(dp[i][t][-1] = \sum_{k\,\in\,t\,\cup\,\{-1\}}dp[i-1][t][k]\timesσ\,-\sum_{k\notin t}dp[i][t\cup \{k\}][k]\)

となります。
求める値は \(\sum_{i=1}^Ndp[L][\{1,2,\dots,N\}][i]+dp[l][\{1,2,\dots,N\}][-1]\) なので、 \(M=\sum_i|S_i|\) として、dpの状態数は \(O(N2^NL)\) で 、遷移に \(O(M)\) かかるので、計算量 \(O(N2^NLM)\) で問題を解くことができます。

実装 (C++ 18ms)