1

この正規表現マッチングの問題の複雑さは気になります。小文字の文字列とマッチング ルールが与えられた場合、そのルールが文字列全体と一致するかどうかを判断します。ルールは、小文字および/または「.」のみを含む簡略化された正規表現です。(ピリオド) および/または '*' (アスタリスク)。ピリオドは任意の小文字と一致し、アスタリスクは先行する要素の 0 個以上と一致する可能性があります。

ここではいくつかの例を示します。

  • isMatch("aa","a") は false
  • isMatch("aa","aa") は true
  • isMatch("aaa","aa") は false
  • isMatch("aa", "a*") は true
  • isMatch("aa", ".*") は true
  • isMatch("ab", ".*") は true
  • isMatch("aab", "c*a*b") は true

この問題は多項式時間で解けると言われています。どうやって？直観的に、「aaaaaaaaaa」を「.*a.*」のような正規表現に一致させると、有限決定論的機械と一致したときに状態遷移を決定するのが難しくなります。コメントはありますか？

ありがとうございました。

4

1 に答える 1

0

これは、動的計画法アルゴリズムを使用して多項式時間で解くことができます。アイデアは、次の形式のクエリに回答することです。

正規表現の最後の n 文字を使用して、文字列の最後の m 文字を照合できますか?

アイデアは、再帰アルゴリズムを使用してから、結果を記憶するか、動的プログラミングを使用して結果をキャッシュすることです。再帰アルゴリズムは次のように機能します。

  • 正規表現が空の場合、空の文字列のみに一致します。
  • 正規表現の 2 番目の文字が * でない場合、文字列の最初の文字が正規表現と一致し、文字列の残りの部分が正規表現の残りの部分と一致する場合、正規表現は文字列と一致します。
  • 正規表現の 2 番目の文字が * の場合、次のいずれかが true の場合、正規表現は文字列と一致します。
    • 正規表現の最初の文字は文字列の最初の文字と一致し、同じ正規表現は文字列の残りの部分と一致します。
    • 正規表現の最初の文字は文字列の最初の文字と一致し、* で囲まれた式が削除された正規表現は文字列の残りの部分と一致します。
    • 正規表現の最初の文字は文字列の最初の文字と一致しませんが、* で囲まれた式を削除して形成された正規表現は文字列と一致します。

これらの各ケースでは、文字列または正規表現のいずれかが短く、再帰呼び出しとは別に O(1) が機能する再帰呼び出しが行われます。可能性のあるサブ問題は Θ(mn) 個 (正規表現の接尾辞と元の文字列の接尾辞の組み合わせごとに 1 つ) しかないため、メモ化を使用すると、この問題は Θ(mn) 時間で解決できます。

お役に立てれば！

于 2013-11-01T03:15:43.540 に答える