Есть ли эффективный способ определить, содержит ли строка подстроку из большого набора c строк?

Question

Например, учитывая строку aaaaaaaaaXyz, я хочу узнать, содержит ли она подстроку, которая находится в наборе строк c {'xy','xyz','zzz','cccc','dddd',....}, который может иметь один миллион членов. Есть эффективный способ?

Answer 1

Прежде всего, вы готовите dictionary. вот так

Set<String> stringSet = Set.of("xy", "xyz", "zzz", "zzy", "cccc", "dddd");
Map<Character, List<String>> dictionary = new HashMap<>();
for (String word : stringSet)
    dictionary.computeIfAbsent(word.charAt(0), k -> new ArrayList<>()).add(word);
System.out.println(dictionary);

вывод:

{c=[cccc], d=[dddd], x=[xyz, xy], z=[zzy, zzz]}

И вы можете использовать этот метод, чтобы узнать.

static boolean contains(String input, Map<Character, List<String>> dictionary) {
    for (int i = 0, max = input.length(); i < max; ++i) {
        char first = input.charAt(i);
        if (dictionary.containsKey(first))
            for (String word : dictionary.get(first))
                if (input.startsWith(word, i))
                    return true;
    }
    return false;
}

Answer 2

Учитывая, что ваш набор для поиска может быть очень большим, я бы рекомендовал просто повторить этот набор и проверить возможное совпадение подстроки:

public boolean containsSubstring(String input, Set<String> subs) {
    boolean match = false;

    for (String sub : subs) {
        if (input.contains(sub)) {
            match = true;
            break;
        }
    }

    return match;
}

Answer 3

С подсказкой Clashsoft , я нашел java реализацию алгоритма Aho-Corasick, который мне нужен, спасибо за Clashsoft