Дано массив с подстроками и строкой, которую я проверяю, если она содержит все их.Самый быстрый способ проверить, содержит ли строка все подстроки
Нужно ли перебирать элементы и проверять с помощью indexOf> = 0 или у вас есть более крутые идеи? Поскольку я должен выполнять эту задачу снова и снова, любые преимущества производительности помогут заблаговременно использовать язык программирования javascript
Вы можете использовать Array.prototype.every (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;
});
Возвращаемое значение является истинным или ложным, конечно.
О, ох, это хорошая функция прототипа, спасибо :-) – Skeec
О, и потому, что вы действительно хотите, чтобы все они содержались внутри вашей строки, вы бы скорее протестировали ее с помощью! = -1 (поскольку indexOf возвращает -1, когда он не найден). Я отредактирую это прямо сейчас. –
Это лучше, чем проверка> = 0? – Skeec
Вы ищете отличную идею и действительно имеете много таких подстрок для тестирования?
Будет хорошей идеей для построения suffix tree для вашей строки, которая имеет сложность поиска только в зависимости от размера подстроки.
Вы получите вниз сложность от O(len(string) * len(substring) * N_substrings) наивного решения (как @ BaneBojanić один), чтобы O(len(string) + len(substring) * N_substrings).
1: Предполагая len(string) * len(substring) сложность для indexOf, это могло бы быть лучше, чем that хотя
Вам нужен алгоритм, поиск в finite set of patterns in one text.
Самый известный из многочисленных вариантов реализации - Aho–Corasick algorithm.
все подстроки одинакового размера случайно? – Andrew
Это отличается, но что вы думаете? Любопытно – Skeec
это зависит от подстроки. вы можете создать регулярное выражение и проверить его. –