Sundayアルゴリズム-JavaScript実現
7289 ワード
Sundayアルゴリズムの概要
_; SundayアルゴリズムはDaniel M.Sundayが1990年に提案した文字列パターンマッチングアルゴリズムです.文字列が指定された文字列を含むかどうかを判定するためです. 平均時間複雑度:O(n)._; 最悪の場合の時間複雑度はO(nm)である.
アルゴリズム解析
の核心思想は、Sundayアルゴリズムは、マッチング過程において、パターンストリングが一致しないことが発見された時に、マッチング失敗時に、メインストリング(main)にマッチする最終位文字の次の文字が注目されます. 1、モード列に該当文字がない場合はそのままスキップします.すなわち移動桁数=モード列長+1です. 2は、モード列に文字がある場合、すなわち移動桁数=文字がメイン列の位置-パターン列に最後に登場する文字の位置です.目的は、文字をモードの文字列の中の文字に揃えて、前から後ろに各文字を比較することです.
JavaScriptコードを貼り付けます.
_; SundayアルゴリズムはDaniel M.Sundayが1990年に提案した文字列パターンマッチングアルゴリズムです.文字列が指定された文字列を含むかどうかを判定するためです. 平均時間複雑度:O(n)._; 最悪の場合の時間複雑度はO(nm)である.
アルゴリズム解析
の核心思想は、Sundayアルゴリズムは、マッチング過程において、パターンストリングが一致しないことが発見された時に、マッチング失敗時に、メインストリング(main)にマッチする最終位文字の次の文字が注目されます. 1、モード列に該当文字がない場合はそのままスキップします.すなわち移動桁数=モード列長+1です. 2は、モード列に文字がある場合、すなわち移動桁数=文字がメイン列の位置-パターン列に最後に登場する文字の位置です.目的は、文字をモードの文字列の中の文字に揃えて、前から後ろに各文字を比較することです.
JavaScriptコードを貼り付けます.
function sunday(main,pattern,ignoreCase)
{
var charSet = {}, // pattern
patternLen = pattern.length,// pattern
mainLen = main.length; // main
//
if(ignoreCase) {
main = main.toLowerCase();
pattern = pattern.toLowerCase();
}
// pattern , :
for (var i = 0; i < patternLen; i++) {
charSet[pattern.charAt(i)] = i;
}
//
for (var i = 0; i <= mainLen-patternLen; ) {
var j = 0;
// , , i , j
while(j<patternLen && main.charAt(i+j) == pattern.charAt(j)) {
j++;
}
if(j == patternLen) {
return i;// main pattern, pattern
} else {
var next = i + patternLen, //
charPos = charSet[main.charAt(next)];//next charSet , undefined
if(charPos > -1) { // next
i = next - charPos; //
} else {
i = next + 1;// next , ,i next
}
}
}
return -1;// main pattern, -1
}