0

给定一个用字符串填充的数组。我需要以下行为：

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

foo 应该等于 ['a']

foo = add_search_string(foo, 'a')

foo 应该等于 ['a'] 因为 'a' 已经是一个搜索字符串

foo = add_search_string(foo, 'ab')

foo 应该等于 ['ab'] 因为 'a' 是 '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

没有一种快速的内置方法可以做到这一点。而且，如果您想测试真正的子字符串而不仅仅是“开始于”，这是一个二次问题，这意味着该函数将花费 n^2 倍的时间，而 n 是键的长度。如果密钥不是太长，它应该可以工作。

于 2012-12-17T22:51:00.583 回答
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 回答
0

对于高性能实现，您将使用后缀树在您的搜索字符串（及其子集）中快速搜索。但是，只有当您真的遇到简单实现的问题（如您的或@nnnnnn 的）时，您才应该这样做，因为 trie 会增加巨大的复杂性层。

于 2012-12-17T23:11:35.943 回答