0

文字列が取り込まれる配列が与えられます。次の動作が必要です。

foo = []
foo = add_search_string(foo, 'a')

foo は ['a'] に等しい必要があります

foo = add_search_string(foo, 'a')

'a' はすでに検索文字列であるため、foo は ['a'] に等しい必要があります。

foo = add_search_string(foo, 'ab')

'a' は 'ab' の部分文字列であり、したがって削除できるため、foo は ['ab'] と等しい必要があります。

foo = add_search_string(foo, 'a')

上記と同じ理由で、foo は ['ab'] と等しくなければなりません

foo = add_search_string(foo, 'c')

foo は ['ab', 'c'] に等しい必要があります

私の関数は次のようになります。

function add_search_string(search_strings, new_search_string) {
    var keep = true;
    var new_search_strings = []
    $.each(search_strings, function(i, search_string) {
        if (new_search_string == search_string) {
            keep = false;
        } else if (search_string.indexOf(new_search_string) >= 0) {
            keep = false;
        }
    });

    if (keep) {
        $.each(search_strings, function(i, search_string) {
            if (new_search_string.indexOf(search_string) == -1) {
                new_search_strings.push(search_string);
            }
        });
        new_search_strings.push(new_search_string);
        search_strings = new_search_strings;
    }
    return search_strings;
}

これを行う「より良い」方法はありますか？

4

4 に答える 4

2

同じ配列を更新し続けることが意図されている場合は、おそらく次のようにします。

function add_search_string(search_strings, new_search_string) {
   var replaced = false;
   for (var i = search_strings.length -1; i >= 0; i--) {
      if (search_strings[i].indexOf(new_search_string) != -1) {
          // string found, so just return
          return search_strings;
      }
      if (new_search_string.indexOf(search_strings[i]) != -1){
          // existing string is a substring of new search string
          // if it already matched another element just remove the current one
          // otherwise replace the current one
          if (replaced)
              search_strings.splice(i,1);
          else
              search_strings[i] = new_search_string;
          replaced = true;
      }
   }
   // if not found add it
   if (!replaced)
      search_strings.push(new_search_string);
   return search_strings;
}

この関数は配列を返しますが、渡した配列も更新するため、関数を呼び出すときに配列を代入する必要はありません。次のように言えます。

add_search_string(foo, 'a');
于 2012-12-17T22:51:34.623 に答える
1

「含む」演算子が必要なため、配列の join() が効率的です。

var str = search_strings.join("|");

// if the new string can't be found
if str.indexOf(new_search_string)==-1 {
    // remove sub-strings of new_search_string (need to start from the top)
    for (var i=search_strings.length-1;i>=0;i--) {
        if (new_search_string.indexOf(search_strings[i])!=-1) {search_strings.splice(i,1);}
    }
    // add new
    search_strings.push(new_search_string);
}
// else new_search_string can be ignored

処理を高速化するために、配列を文字列の長さで並べ替えるかフィルター処理し、new_search_string より短い文字列のみをループすることも検討してください。

于 2012-12-17T23:39:36.420 に答える
1

これを行うための組み込みの高速な方法はありません。また、「で始まる」だけでなく、真の部分文字列をテストしたい場合は、キーの長さ n で関数が n^2 倍長くかかることを意味する二次問題です。キーが長すぎない場合でも機能するはずです。

于 2012-12-17T22:51:00.583 に答える
0

パフォーマンスの高い実装では、サフィックス ツリーを使用して、検索文字列 (およびそのサブセット) をすばやく検索します。ただし、単純な実装 (あなたのものや @nnnnnn のものなど) で実際に問題に直面した場合にのみ、これを行う必要があります。

于 2012-12-17T23:11:35.943 に答える