regex - Scala での単純化された正規表現マッチング

Question

Scala演習として、一致する単純な正規表現を作成しようとしています。簡単にするために、一致する文字列は ASCII であり、正規表現は ASCII 文字と 2 つのメタ文字で構成されると仮定し.ます*。(明らかに、正規表現ライブラリは使用していません)。

これは私のシンプルで遅い（指数関数的な）ソリューションです。

def doMatch(r: 文字列、s: 文字列): ブール値 = {
  if (r.isEmpty) s.isEmpty
  そうでなければ (r.length > 1 && r(1) == '*') star(r(0), r.tail.tail, s)
  else if (!s.isEmpty && (r(0) == '.' || r(0) == s(0))) doMatch(r.tail, s.tail)
  そうでなければ偽
}

def star(c: Char, r: 文字列, s: 文字列): Boolean = {
  if (doMatch(r, s)) 真
  else if (!s.isEmpty && (c == '.' || c == s(0))) star(c, r, s.tail)
  そうでなければ偽
}

今はそれを改善したいと思います。「純粋な」Scalaコードの〜10〜15行で単純な多項式ソリューションを提案できますか?