文字列の完全一致を見るのは簡単だけど、ワイルドカードも考えるとなると、一気に難しくなる……ような気がしていました。けれど、再帰を使ってみると、意外と簡単に実装できたので、嬉しくなって記事にしちゃいました。
アルゴリズム自体はシンプルだったので、今でも実用されている手続き型言語の中で最も文字列の扱いが面倒そうなCで書いてみましたが、1文字ずつ文字を見ていくなら、案外、Cで書いた方が下手に別の言語で書くよりシンプルかもしれないです。
また、再帰を使うのでせっかくだからSchemeでも書いてみました。
ここでいう、ワイルドカードでのマッチングは、以下の仕様とします。
-
wildcard_matching(wildcard, target)において、wildcardとtargetの文字列がマッチしていれば1を、していなければ0を返す。 - wildcardとtargetが同じ文字列であれば、それらはマッチしている。その際、wildcard中の
?は任意の1文字として扱われる。*は任意の0文字以上として扱われる。?や*にはエスケープシーケンスはない。 - wildcardがtargetの一部のみとマッチしている場合は、マッチしているとは扱わない。すなわち、
xxxはaxxxaとマッチしていない。*xxx*とaxxxaはマッチしている。 - 空文字列
""と空文字列""はマッチしている。 - マルチバイト文字は考慮していない。
実装はこちら。
追記: 間違ってるんちゃうかとコメント欄で指摘いただいたのでC, Schemeとも修正
wildcard.c
int wildcard_match(const char *wildcard, const char *target)
{
const char *pw = wildcard, *pt = target;
while(1){
if(*pt == 0){
while(*pw == '*') pw++;
return *pw == 0;
}
else if(*pw == 0) return 0;
else if(*pw == '*'){
return *(pw+1) == 0 || wildcard_match(pw, pt + 1)
|| wildcard_match(pw + 1, pt);
}
else if(*pw == '?' || (*pw == *pt)){
pw++;
pt++;
continue;
}
else return 0;
}
}
1文字ずつ見ているんですが、*が出ると、再帰で、wildcardのポインタを1文字進めたものとのマッチングと、targetのポインタを1文字進めたものとのマッチングを見ています。
また、wildcardの末尾に*が出た場合は、これ以降はすべてマッチしています。
Schemeではこんな感じ。
wildcard.scm
(define (wildcard_match wildcard target)
(define (match wildcard target)
(cond
((null? target) (or (null? wildcard) (and (char=? (car wildcard) #\*) (match (cdr wildcard) target))))
((null? wildcard) #f)
((or (char=? (car wildcard) #\?) (char=? (car wildcard) (car target)))
(match (cdr wildcard) (cdr target)))
((char=? (car wildcard) #\*)
(or (null? (cdr wildcard))
(match wildcard (cdr target))
(match (cdr wildcard) target)))
(else #f)))
(match (string->list wildcard) (string->list target)))