ワイルドカードのマッチアルゴリズム
*(ワイルドーカード)マッチの実装どうするか
正規表現にするにはサニタイズが必要
例えば.や?といった文字列は正規表現でも特別な意味を持ってしまう
欲張り法で実装出来るのでは？
*A*B*みたいな文字列がある時、
最初に*A*を取り出す
これは文字列中にAが含まれていれば良いということ
文字列がAを含むなら、カーソルをAの後ろにセットして次へ
含まないなら終了
次にB*を取り出す
これは残りの文字列にBが含まれていれば良いということ
文字列がBを含むなら、文字列はマッチした
含まないなら終了
A*Bみたいな文字列がある時、
最初にA*を取り出す
これは文字列がAから始まるということ
文字列がAから始まるなら、カーソルをAの後ろにセットして次へ
そうでなければ終了
次にBを取り出す
これは残りの文字列がBで終わるということ
文字列がBで終わるなら、文字列はマッチした
そうでなければ終了
実際のコードでは、まずp = pattern.split('*')する
先頭から文字列を探しながらカーソルを右に移動していく
1. もし先頭であれば、A*を取り出したのと同じ。つまりAから始まる必要がある
2. もし中間であれば、*B*を取り出したのと同じ。つまりBが含まれてさえいれば良い
3. もし末尾であれば、*Bを取り出したのと同じ。つまりBで終わる必要がある
最後まで条件を満たしたならば、文字列はマッチしたことになる
ポイントは、1かつ3があり得ること。つまりpatternに*が含まれない場合もある
サンプルコード
code:ts
function matchWildcard(pattern: string, str: string) {
const needs = pattern.split("*");
if (needs.length === 1) {
return pattern === str;
}
const head = needs.shift()!;
const tail = needs.pop()!;
let cursor = 0;
if (!str.startsWith(head)) {
return false;
}
cursor = head.length;
for (let n = 0; n < needs.length; n++) {
const index = str.indexOf(needsn, cursor); if (index === -1) return false;
cursor = index + needsn.length; }
if (!str.substring(cursor).endsWith(tail)) {
return false;
}
return true;
}