0

'。'をサポートする正規表現マッチングを実装します。と '*'。

'。' 任意の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

著者は次の解決策を示していますが、これは本当に美しいです。

bool isMatch(const char *s, const char *p) {
  assert(s && p);
  if (*p == '\0') return *s == '\0';

  // next char is not '*': must match current character
  if (*(p+1) != '*') {
    assert(*p != '*');
    return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);
  }
  // next char is '*'
  while ((*p == *s) || (*p == '.' && *s != '\0')) {
    if (isMatch(s, p+2)) return true;
    s++;
  }
  return isMatch(s, p+2);
}

著者はまた、いくつかのさらなる考えを与えます：

注意深く考えると、上記のコードが指数関数的に複雑に実行される場合があります。

いくつかの例を考えていただけますか？上記のコードをより効率的にするにはどうすればよいですか？

文字列sとpの長さがそれほど大きくないのに、結果を得るのに長い時間がかかるケースを1つ思いつきました。

s [] = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" p [] = "a * a * a * a * a * a * a * a * a * a * a * a * a * a * a * a * a * a * a * a * a * a * a * a * a * b "

誰かが私がこの答えを確認するのを手伝ってもらえますか？この種の極端なテストの質問を見つけることをどのように考えるのですか？

4

2 に答える 2

2

ケースが指数関数的な動作を示す理由を理解する最善の理由は、最初にコードを少し試してから、そこからいくつかの経験的データを収集して仮説を立てることです。

まず、簡単な「ロギング」を追加しましょう。

#include <cassert> 
#include <cstdio>
using namespace std;

int count = 0;

bool isMatch(const char *s, const char *p) {
    printf("%5d   %s   %s\n", count++, s, p);  
    .
    .
    .

各実験の前にカウントをリセットすることを確認して、いくつかの実験を実行しましょう (実際のコードではグローバル変数を避ける必要があることを思い出してください:))

isMatch("a", "a*b");
isMatch("aa", "a*a*b");
isMatch("aaa", "a*a*a*b");
isMatch("aaaa", "a*a*a*a*b");
isMatch("aaaaa", "a*a*a*a*a*b");
isMatch("aaaaaa", "a*a*a*a*a*a*b");

それぞれの出力を見て、それぞれに対して生成された行数を見て、「文字列を長くすると、再帰呼び出しの数はどのように増加するのか?」と自問することができます。(古典的な経験的アルゴリズム分析!)

aaaここでケースを作成しました: http://ideone.com/8t2kS

34 ステップかかったことがわかります。出力を見てください。マッチングの性質についての洞察が得られるはずです。そして、長さが長くなる文字列を試してみてください。楽しい実験。

于 2012-09-18T15:50:24.800 に答える
2

これは、再帰降下による正規表現マッチングの実装が異常な動作につながる典型的なケースです。

これを実装する正しい方法は、正規表現を非決定論的なステート マシンに変えることです。（かなり）多くのコードが必要ですが、任意の正規表現に対して線形時間で実行されます。

これは、この主題に関する一流の記事です。

乾杯！

于 2012-09-18T04:09:03.930 に答える