テキストと正規表現が与えられたとき、テキストから正規表現にマッチする最短
文字列を検索する問題を考える。この問題に対し、著者らは、O(mn)時間で動作するアルゴリズムを開発した。ここで、nはテキストの長さ、mは正規表現の長さを表す。本論文では、このアルゴリズムを並列化に向け拡張し、実験的に評価する。