2024-04-20 追記：Python での実装例を掲載していましたが、Python の正規表現ライブラリには計算量上の弱点があるようなので削除しました。

正規表現ライブラリが使える言語では、文字列 \(T\) が文字列 \(S\) の部分列であるかの判定を楽に実装できます。例えば、NRT が文字列 \(S\) の部分列であることは、N.*R.*T というパターンが \(S\) に現れることと同値です。

なお、与えられた \(S\) の末尾に X を付ければ、問題文中の二つの方法のうち二つ目を無視できます。

実装例（Python）