非常に縮小されたパターン言語では、質問のペーストビン リンクと jpmc26 のコメントはほとんどそこにあります。主な質問は、入力文字列の文字通りの左端と右端が一致するかどうかです。それらが存在し、両方に少なくとも 1 つの が含まれている場合*、文字列は一致します (その星が付いている他の文字列の中間リテラル テキストをいつでも一致させることができるため)。特殊なケースが 1 つあります。1 つだけが空の場合 (接尾辞と接尾辞を削除した後)、もう一方が完全に*s で構成されていれば、一致する可能性があります。
?もちろん、文字列の末尾が一致するかどうかを確認するときは、1 文字のワイルドカードと文字クラスも考慮する必要があります。単一文字のワイルドカードは簡単です。他の文字が何であれ常に一致するため、失敗することはありません。それが文字クラスで、もう一方が単なる文字の場合、その文字がクラスに含まれているかどうかを確認する必要があります。それらが両方ともクラスである場合、クラスの共通部分 (単純集合共通部分) をチェックする必要があります。
JavaScript でのすべてを次に示します (コードのコメントをチェックして、上で概説したアルゴリズムがコードにどのようにマップされるかを確認してください)。
var trueInput = [
{ left: 'prefix*', right: 'prefix:extended*' },
{ left: '*suffix', right: '*:extended:suffix' },
{ left: 'left*right', right: 'left*middle*right' },
{ left: 'a*b*c', right: 'a*b*d*b*c' },
{ left: 'hello*', right: '*ok' },
{ left: '*', right: '*'},
{ left: '*', right: '**'},
{ left: '*', right: ''},
{ left: '', right: ''},
{ left: 'abc', right: 'a*c'},
{ left: 'a*c', right: 'a*c'},
{ left: 'a[bc]d', right: 'acd'},
{ left: 'a[bc]d', right: 'a[ce]d'},
{ left: 'a?d', right: 'acd'},
{ left: 'a[bc]d*wyz', right: 'abd*w[xy]z'},
];
var falseInput = [
{ left: 'prefix*', right: 'wrong:prefix:*' },
{ left: '*suffix', right: '*suffix:wrong' },
{ left: 'left*right', right: 'right*middle*left' },
{ left: 'abc', right: 'abcde'},
{ left: 'abcde', right: 'abc'},
{ left: 'a[bc]d', right: 'aed'},
{ left: 'a[bc]d', right: 'a[fe]d'},
{ left: 'a?e', right: 'acd'},
{ left: 'a[bc]d*wyz', right: 'abc*w[ab]z'},
];
// Expects either a single-character string (for literal strings
// and single-character wildcards) or an array (for character
// classes).
var characterIntersect = function(a,b) {
// If one is a wildcard, there is an intersection.
if (a === '?' || b === '?')
return true;
// If both are characters, they must be the same.
if (typeof a === 'string' && typeof b === 'string')
return a === b;
// If one is a character class, we check that the other
// is contained in the class.
if (a instanceof Array && typeof b === 'string')
return (a.indexOf(b) > -1);
if (b instanceof Array && typeof a === 'string')
return (b.indexOf(a) > -1);
// Now both have to be arrays, so we need to check whether
// they intersect.
return a.filter(function(character) {
return (b.indexOf(character) > -1);
}).length > 0;
};
var patternIntersect = function(a,b) {
// Turn the strings into character arrays because they are
// easier to deal with.
a = a.split("");
b = b.split("");
// Check the beginnings of the string (up until the first *
// in either of them).
while (a.length && b.length && a[0] !== '*' && b[0] !== '*')
{
// Remove the first character from each. If it's a [,
// extract an array of all characters in the class.
aChar = a.shift();
if (aChar == '[')
{
aChar = a.splice(0, a.indexOf(']'));
a.shift(); // remove the ]
}
bChar = b.shift();
if (bChar == '[')
{
bChar = b.splice(0, b.indexOf(']'));
b.shift(); // remove the ]
}
// Check if the two characters or classes overlap.
if (!characterIntersect(aChar, bChar))
return false;
}
// Same thing, but for the end of the string.
while (a.length && b.length && a[a.length-1] !== '*' && b[b.length-1] !== '*')
{
aChar = a.pop();
if (aChar == ']')
{
aChar = a.splice(a.indexOf('[')+1, Number.MAX_VALUE);
a.pop(); // remove the [
}
bChar = b.pop();
if (bChar == ']')
{
bChar = b.splice(b.indexOf('[')+1, Number.MAX_VALUE);
b.pop(); // remove the [
}
if (!characterIntersect(aChar, bChar))
return false;
}
// If one string is empty, the other has to be empty, too, or
// consist only of stars.
if (!a.length && /[^*]/.test(b.join('')) ||
!b.length && /[^*]/.test(b.join('')))
return false;
// The only case not covered above is that both strings contain
// a * in which case they certainly overlap.
return true;
};
console.log('Should be all true:');
console.log(trueInput.map(function(pair) {
return patternIntersect(pair.left, pair.right);
}));
console.log('Should be all false:');
console.log(falseInput.map(function(pair) {
return patternIntersect(pair.left, pair.right);
}));
これは最もきちんとした実装ではありませんが、機能し、(願わくば) まだかなり読みやすいです。最初と最後をチェックすると、コードの重複がかなりあります（これはreverse、最初のチェック後に簡単に軽減できますが、それは物事を不明瞭にするだけだと思いました）。他にも大幅に改善できる点はたくさんあると思いますが、ロジックはすべて整っていると思います。
いくつかの注意事項: 実装では、パターンが適切にフォーマットされている (一致しない開きかっこがない) ことを前提としています。また、配列交差コードはコンパクトであるため、この回答から取得しました。必要に応じて、その効率を確実に向上させることができます。
これらの実装の詳細に関係なく、複雑さの質問にも答えることができると思います。外側のループは、一度に 1 文字ずつ、両方の文字列を同時に処理します。これが線形複雑性です。文字クラスのテストを除いて、ループ内のすべてを一定時間で実行できます。1 つの文字が文字クラスで、もう 1 つの文字がそうでない場合、文字がクラスに含まれているかどうかを確認するには、(クラスのサイズをパラメーターとして) 線形時間が必要です。ただし、クラス内の各文字は外側のループの反復が 1 つ少ないことを意味するため、これは 2 次にはなりません。それで、それはまだ線形です。したがって、最もコストがかかるのは、2 つの文字クラスの交差です。これは線形時間よりも複雑かもしれませんが、最悪の場合はO(N log N): 結局のところ、両方の文字クラスを並べ替えて、線形時間で交差点を見つけることができます。.charCodeAt(0)文字クラスの文字をUnicodeコードポイント（ JSの）またはその他の数値にハッシュすることで、全体的な線形時間の複雑さを得ることができると思います-ハッシュされたセットの交差点を線形時間で見つけることができます。ですから、どうしてもやりたいのであれば、 まで降りられるはずだと思いますO(N)。
とは何Nですか？上限は両方のパターンの長さの合計ですが、ほとんどの場合、実際にはそれよりも短くなります (両方のパターンのプレフィックスとサフィックスの長さに依存します)。
私のアルゴリズムが欠落しているエッジケースを教えてください。また、提案された改善がコードの明瞭さを改善するか、少なくとも低下させない場合は、私も満足しています。
これは JSBin のライブ デモです(そこに貼り付けてくれた chakrit に感謝します)。
編集:ダニエルが指摘したように、私のアルゴリズムが見逃している概念的なエッジケースがあります。(先頭と末尾を削除する前後に) 一方の文字列に no が含まれてい*て、もう一方の文字列に含まれている場合、2 つの文字列が衝突する場合があります。残念ながら、その問題に対応するようにコード スニペットを調整する時間は今のところありませんが、解決方法の概要を説明することはできます。
文字列の両端を削除した後、両方の文字列が空であるか、*少なくとも*. 自明ではない唯一のケースは、1 つの文字列に が含まれている*が、もう 1 つの文字列には含まれていない (空であるかどうかに関係なく) 場合です。次に行う必要があるのは、両方の文字列を左から右にもう一度歩くことです。*Aを含む文字列と*Bを含まない文字列を呼び出します。
A を左から右に歩き、すべてをスキップします( 、文字クラス、およびリテラル文字*のみに注意してください)。?関連するトークンのそれぞれについて、左から右に、それが B で一致するかどうか (最初の出現で停止) をチェックし、B カーソルをその位置に進めます。B で見つからないトークンが A で見つかった場合、それらは一致しません。A の各トークンの一致を見つけることができれば、それらは一致します。この方法では、バックトラッキングが含まれないため、引き続き線形時間を使用します。2 つの例を次に示します。これら 2 つは一致する必要があります。
A: *a*[bc]*?*d* --- B: db?bdfdc
^ ^
A: *a*[bc]*?*d* --- B: db?bdfdc
^ ^
A: *a*[bc]*?*d* --- B: db?bdfdc
^ ^
A: *a*[bc]*?*d* --- B: db?bdfdc
^ ^
これら 2 つは一致しないはずです。
A: *a*[bc]*?*d* --- B: dbabdfc
^ ^
A: *a*[bc]*?*d* --- B: dbabdfc
^ ^
A: *a*[bc]*?*d* --- B: dbabdfc
^ ^
A: *a*[bc]*?*d* --- B: dbabdfc
!
?が 2 番目の の前に一致する可能性dはなく、その後は Bに Adの最後のものに対応するものがないため、失敗します。d
時間をかけて文字列をトークン オブジェクトに適切に解析していれば、これを現在の実装に追加するのはおそらく簡単でしょう。しかし、今度は、それらの文字クラスを解析するという手間をもう一度やり直さなければなりません。この追加の概要が十分に役立つことを願っています。
PS: もちろん、私の実装ではメタ文字のエスケープも考慮されておらず、*文字クラス内で窒息する可能性があります。
