2026-10-18
shortest.c
#include <stdio.h>
static const char *here(const char *re, const char *s) {
if (re[0] == '\0') return s;
if (re[1] == '*') {
do {
const char *end = here(re + 2, s);
if (end) return end;
} while (*s != '\0' && (*s++ == re[0] || re[0] == '.'));
return NULL;
}
if (re[0] == '$' && re[1] == '\0') return *s == '\0' ? s : NULL;
if (*s != '\0' && (re[0] == '.' || re[0] == *s)) return here(re + 1, s + 1);
return NULL;
}
int main(void) {
const char *s = "axbxb";
const char *a = here("a.*b", s), *b = here("a.*b$", s);
printf("%.*s %.*s\n", (int)(a - s), s, (int)(b - s), s);
}
これは何を出力するでしょうか?
Answer
axb axbxb の1行です。
here は、re が s の先頭から始まる部分に一致すれば一致の終わりの位置を返し、一致しなければ NULL を返します。re[1] == '*' の分岐では do の本体が条件より先に実行されるので、* に0文字を受け持たせる場合が最初に試され、残りのパターン re + 2 が合わなかったときにだけ s が1文字進みます。* が受け持つ文字数は、少ない方から順に試されます。
a.*b では、a が合ったあとの .* がまず0文字のまま b を xbxb の先頭に当てて失敗し、x を1文字受け持ったところで b が合います。残りのパターンが空になって3文字目の後ろの位置が返るので、1つ目は axb です。Perl をはじめ多くの正規表現ライブラリでは * が長い方から試される(貪欲な一致)ため、axbxb と読みたくなりますが、このマッチャは最初に見つけた一致で止まります。
a.*b$ も axb までは同じように進みますが、残りの $ は xb の手前では文字列の終わりに当たらず、NULL を返します。この失敗が .* のループまで戻ると、.* は受け持つ文字を1つずつ増やしてやり直し、xbx の3文字を受け持ったところで b と $ が両方合います。2つ目が axbxb 全体になるのは、* が長い一致を好むからではなく、短い候補がどれも後ろの $ で振り落とされたからです1。
- この形のマッチャは Rob Pike が書いたもので、Brian Kernighan が『Beautiful Code』(2007年)の章で紹介しています。元のコードは一致したかどうかだけを返すので、どの長さで一致したかは表に出ません。