检查字符串是否包含所有子字符串的最快方法

Fastest way to check if string contains all substrings

本文关键字：字符串 方法 是否 包含所 检查      更新时间：2023-09-26

Given是一个包含子字符串和字符串的数组，如果它包含所有子字符串，我将对其进行检查。

我必须迭代元素并使用indexOf>=0进行检查吗？或者你有什么更酷的想法吗？因为我必须一次又一次地完成这项任务，所以任何性能优势都会有所帮助，这要归功于预先编程语言是javascript

您可以使用Array.prototype.eevery（callback[，thisArg]）；点击此处阅读更多信息：https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/every

基本上，对于您的示例，它将是：

arr.every(function(element){
    return yourstring.indexOf(element) != -1;
});

当然，返回值要么为true，要么为false。

您正在寻找一个很酷的想法，并且真的有很多这样的子字符串要测试吗？

然后，从性能角度来看，为字符串构建后缀树是一个好主意，它的查找复杂度仅取决于子字符串的大小。

您将把朴素解（如@BaneBojanić的解）的复杂性从O(len(string) * len(substring) * N_substrings)1降低到O(len(string) + len(substring) * N_substrings)。

1：假设indexOf的len(string) * len(substring)复杂度，它可能比的复杂度更好

您需要一种在一个文本中搜索有限模式集的算法。

最为人所知的有许多实现的算法是Aho–Corasick算法。

相关文章：