Sundayアルゴリズム-JavaScript実現


Sundayアルゴリズムの概要
_; 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
  }