Быстрый алгоритм для определения, содержит ли строка какую-либо строку в данном массиве

Question

У меня есть список из 50 ключевых слов и около 50000 строк.Я проверяю каждую строку, если она содержит хотя бы одно из ключевых слов.Меня не интересует соответствующее ключевое слово или количество подходящих ключевых слов.Я только хочу, чтобы "true" или "false" возвращались как можно быстрее.

Итак, держу пари, что существует алгоритм, который намного превосходит мою текущую версию LINQ:

class MyEnumerableExtension
{
    public static bool ContainsAny(this string searchString, IEnumerable<string> keywords)
    {
        return keywords.Any(keyword => searchString.Contains(keyword))
    }
}

bool foundAny = "abcdef".ContainsAny(new string[] { "ac", "bd", "cd" } );

Answer 1

Разве это не то же самое, что ваш второй вопрос сегодня Эффективный алгоритм поиска всех ключевых слов в тексте , за исключением измененного, чтобы возвращать, когда совпадение было найдено?

Answer 2

Быстрый анализ показывает, что вы итеративно ищете ключевые слова. Если бы вы могли найти за один проход все ключевые слова, ваш алгоритм должен быть в целом улучшен. Выражение Regex может сделать это и связать его с опцией «Compiled», и вы должны начать видеть повышение производительности (потому что оно передаст строку для всех ключевых слов). Но это принесет пользу только вам, если у вас есть несколько ключевых слов. Вот быстрая идея, чтобы помочь вам в этом, но учтите, что на самом деле я не проверял производительность по вашему алгоритму.

        string[] keywords = { "ac", "bd", "cd" };
        string[] tosearch = { "abcdef" };
        string pattern = String.Join("|", keywords);
        Regex regex = new Regex(pattern, RegexOptions.Compiled);
        foundAny = regex.IsMatch(String.Join("|", tosearch));

Также обратите внимание, что это работает до тех пор, пока ваши ключевые слова не содержат каких-либо специальных символов Regex (а ваши строки поиска не содержат символа канала. Однако специальные символы могут быть преодолены с помощью escape-последовательностей, а строки поиска - нет. надо присоединиться, как я сделал.

Answer 3

Вы можете реализовать алгоритм Кнута-Морриса-Пратта .

Answer 4

Существует несколько алгоритмов для поиска в тексте набора подстрок.