各 \(S_i\) に対して、

• \(S_i\) に部分列として含まれる \(T\) の最長の接頭辞の長さを \(A_i\) 、
• \(S_i\) に部分列として含まれる \(T\) の最長の接尾辞の長さを \(B_i\)

と定め、まず数列 \(A = (A_1, A_2, \ldots, A_N)\) と数列 \(B = (B_1, B_2, \ldots, B_N)\) を計算します。

ある \(i\) について \(A_i\) を計算するには、\(S_i\)を 先頭の文字から順に見ていき、\(T\) の文字が先頭何文字まで \(S_i\) の中に現れるかを求めれば良いです。 より具体的には、

• まず最初の目標の文字を \(T\) の \(1\) 文字目 \(T_1\) に設定して、\(S_i\) を先頭から順に見ていきます。

• \(S_i\) を見ていく過程で目標の文字 \(T_1\) が現れたら、目標の文字を \(T\) の \(2\) 文字目 \(T_2\) に変更して、\(S_i\) の続きを見ていきます。

• その過程でまた目標の文字 \(T_2\) を見つけたら、目標の文字を \(T\) の \(3\) 文字目 \(T_3\) に変更して、\(S_i\) の続きを見ていきます。

• \(\cdots\)

という手順を行い、\(S_i\) を全て調べ終わるまでに、目標の文字を見つけた回数を \(A_i\) とすれば良いです。 この手順では、\(S_i\) を先頭から \(1\) 回走査するので、かかる時間は \(O(|S_i|)\) です。よって、この方法で数列 \(A\) 全体を求めるのにかかる時間は \(O(\sum_{i = 1}^N |S_i|)\) と評価できますが、\(\sum_{i = 1}^N |S_i| \leq 5 \times 10^5\) なので、十分高速です。

数列 \(B\) を求めるには、各文字列 \(S_i\) と \(T\) を前後反転したのち、数列 \(A\) を求めたのと同様の処理をすれば良いです。

また、\(B_i = j\) となるような \(i\) の個数を \(C_j\) として定め、 数列 \(C = (C_0, C_1, \ldots, C_{|T|})\) を、\(O(N)\) 時間で前計算しておきます。

以上の準備をもとに本題に入ります。 \(1\) 以上 \(N\) 以下の整数のペア \((i, j)\) が問題文中の条件を満たす、つまり、\(S_i\) と \(S_j\) を連結した文字列が \(T\) を部分列として含むとき、ペア \((i, j)\) を良いペアと呼ぶことにし、本問題の答えである、良いペアの個数を数えましょう。

まず、\(i\) を固定したときの、\((i, j)\) が良いペアとなる \(j\) の個数を求めることを考えます。 \((i, j)\) が良いペアであることは、\(A_i + B_j \geq |T|\) と同値なので、 \((i, j)\) が良いペアとなる \(j\) は、\(B_j\) が \(l_i \coloneqq |T| - A_i\) 以上であるような \(j\) です。 そして、\(B_j\) が \(l_i\) 以上であるような \(j\) の個数は、数列 \(C\) を用いて \(\sum_{k = l_i}^{|T|} C_k\) と表せます。 よって、これを全ての \(i\) について足し合わせることで、本問題の答えは

\[\sum_{i = 1}^N \sum_{k = l_i}^{|T|} C_k \tag{1}\]

と得られます。上式 (1) で和をとる項の個数は

\[ \begin{aligned} \sum_{i = 1}^N (|T| - l_i + 1) = \sum_{i = 1}^N (|T| - (|T| - A_i)+ 1) = \sum_{i = 1}^N A_i + N \leq \sum_{i = 1}^N |S_i| + N \leq 5 \times 10^5 + 5 \times 10^5 \end{aligned} \]

と十分小さいので、式 (1) を、たとえば \(2\) つのシグマ記号に対応した \(2\) 重ループなどで愚直に計算しても十分高速です。

以下に、C++ 言語による正解例を記載します。

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll n;
string s[500001], t;
ll a[500001], b[500001], c[500001];

ll calc(const string &s, const string &t)
{
  ll g = 0;
  for(auto c : s){
    if(g >= (int)t.size()) break;
    if(c == t[g]) g++;
  }
  return g;
}

int main(void){
  cin >> n >> t;
  for(int i = 1; i <= n; i++) cin >> s[i];
  
  for(int i = 1; i <= n; i++) a[i] = calc(s[i], t);
  reverse(t.begin(), t.end());
  for(int i = 1; i <= n; i++){
    reverse(s[i].begin(), s[i].end());
    b[i] = calc(s[i], t);
    c[b[i]]++;
  }
  
  ll ans = 0;
  for(int i = 1; i <= n; i++){
    ll l = (ll)t.size() - a[i];
    for(int j = l; j <= t.size(); j++){
      ans += c[j];
    }
  }
  cout << ans << endl;
  
  return 0;
}