Namaran

Code daily. Without assist.

2026-10-18

match.c

static bool matchhere(const char *re, const char *text);

bool match(const char *re, const char *text) {
}

^ $ . * だけを扱う正規表現 re が、文字列 text のどこかの部分に一致するかを返す match を書いてください。. は任意の1文字、c* は直前の1文字 c の0回以上の繰り返し(c が . なら任意の文字の繰り返し)に一致し、パターン先頭の ^ は一致が text の先頭から始まること、パターン末尾の $ は一致が text の終わりで終わることを表します。ほかの文字はその文字自身に一致します。^ を含まない re が text の先頭から始まる部分に一致するかを返す matchhere は、定義済みのものを使ってください。re が空の部分に一致できるなら、text が空文字列でも true を返します。

入力例 1

match("^ab", "cab")

出力例 1

false

入力例 2

match("c.t", "concat")

出力例 2

true

入力例 3

match("x*", "")

出力例 3

true
Reference
bool match(const char *re, const char *text) {
    if (re[0] == '^') {
        return matchhere(re + 1, text);
    }
    do {
        if (matchhere(re, text)) {
            return true;
        }
    } while (*text++ != '\0');
    return false;
}

^ で始まるパターンは text の先頭でしか一致できないので、^ を外した残りを matchhere に渡し、その結果をそのまま返します。それ以外のパターンは一致がどこから始まってもよいので、text の各位置を先頭として matchhere を順に呼び、どこかで一致した時点で true を返します。

試す位置には、終端の '\0' を指す位置も含めます。x* や $ のように空の部分に一致できるパターンは、文字が1つも残っていない位置でも一致するからです。参考実装が条件を後に置く do〜while で書いてあるのはこのためで、for (; *text != '\0'; text++) で回すと、終端の位置を試す前にループを抜けます。すると match("x*", "") は一度も matchhere を呼ばずに false を返し、match("$", "ab") も false になります。

掲載したのは参考実装で、唯一の正解ではありません。for (;; text++) の中で matchhere を呼んでから *text == '\0' なら抜ける、という順に書いても同じ位置を試せます。