Каков типичный алгоритм поиска строки в строке?

Question

У меня недавно был вопрос на собеседовании, который звучал примерно так:

Учитывая большую строку (стог сена), найти подстроку (иглу)?

Я был немного озадачен, чтобы найти достойное решение.

Каков наилучший способ приблизиться к этому, который не имеет плохой временной сложности?

Answer 1

Мне нравится алгоритм Бойера-Мура . Это особенно интересно реализовать, когда в стоге сена есть много игл (например, шаблоны вероятного спама в корпусе электронной почты).

Answer 2

Вы можете использовать алгоритм Кнута-Морриса-Пратта , который равен O (n + m), где n - длина строки "стога сена", а m - длина строки поиска.

Answer 3

Общая проблема поиск строки ; Есть много алгоритмов и подходов в зависимости от характера приложения.

• Кнут-Моррис-Пратт , ищет строку в другой строке
• Бойер-Мур , другая строка в строке поиска
• Ахо-Corasick ; ищет слова из справочного словаря в заданном произвольном тексте

Некоторые расширенные структуры данных индекса также используются в других приложениях. Суффикс-деревья широко используются в биоинформатике; здесь у вас есть один длинный ссылочный текст, а затем у вас есть много произвольных строк, для которых вы хотите найти все вхождения. Как только индекс (то есть дерево) построен, поиск шаблонов может быть выполнен довольно эффективно.

Что касается ответа на собеседование, я думаю, что лучше также показать широту. Знать обо всех этих различных алгоритмах и о том, какие конкретные цели они служат лучше, вероятно, лучше, чем знать только один алгоритм наизусть.

Answer 4

Я не верю, что есть что-то лучше, чем смотреть на стог сена по одному символу за раз и пытаться сопоставить их со стрелкой.

Это будет иметь линейную сложность по времени (в зависимости от длины стога сена).).Он может ухудшиться, если длина иглы будет примерно такой же, как у стога сена, и у нее будет общий общий и повторяющийся префикс.

Answer 5

A типичный алгоритм будет выглядеть следующим образом со строковыми индексами в диапазоне от 0 до M-1.

Возвращает либо позицию совпадения, либо -1, если не найден.

foreach hpos in range 0 thru len(haystack)-len(needle):
    found = true
    foreach npos in range 0 thru len(needle):
        if haystack[hpos+npos] != needle[npos]:
            found = false
            break
    if found:
        return hpos
return -1

Он имеет разумную производительность, так как он проверяет только столько символов в каждой позиции стога сена, сколько необходимо, чтобы обнаружить, что нет шансов на совпадение.

Это не обязательно самый эффективный алгоритм, но если ваш интервьюер ожидает, что вы знаете все высокопроизводительные алгоритмы, вы нереалистичны (то есть дураки). Хороший разработчик хорошо знает основы, и как найти продвинутый материал , где необходимо (например, когда есть проблемы с производительностью, не раньше).

Диапазон производительности между O (a) и O (ab) зависит от фактических данных в строках, где a и b - длины стога и сена соответственно.

Одним из возможных улучшений является сохранение в цикле npos первого местоположения, большего, чем hpos, где символ соответствует первому символу стрелки.

Таким образом, вы можете пропустить hpos вперед в следующей итерации, поскольку знаете, что до этого момента возможного совпадения не может быть. Но опять же, это может быть необязательно, в зависимости от ваших требований к производительности. Вы должны выработать баланс между скоростью и ремонтопригодностью самостоятельно.

Answer 6

Эта проблема обсуждается в Взлом вопросов для интервью в Google - лицо A . Их образец решения:

bool hasSubstring(const char *str, const char *find) {
    if (str[0] == '\0' && find[0] == '\0')
        return true;

    for(int i = 0; str[i] != '\0'; i++) {
        bool foundNonMatch = false;
        for(int j = 0; find[j] != '\0'; j++) {
            if (str[i + j] != find[j]) {
                foundNonMatch = true;
                break;
            }
        }
        if (!foundNonMatch)
            return true;
    }
    return false;
}

Answer 7

я думаю, что самый простой способ - это "стог сена" .Contains ("игла");) Просто весело, не принимайте это всерьез. Я думаю, что вы уже получили свой ответ.

Answer 8

Вот представление нескольких алгоритмов (бесстыдно связанных с Университетом Гумбольдта). содержит несколько хороших алгоритмов, таких как Boyer More и Z-box.

Я использовал алгоритм Z-Box , нашел, что он работает хорошо и эффективнее, чем Boyer-More, однако мне нужно некоторое время, чтобы обернуть его вокруг.