Что такое типичный алгоритм для нахождения строки в строке?

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

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

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

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

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

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

• Knuth-Morris-Pratt, поиск строки внутри другой строки
• Boyer-Moore, поиск другой строки внутри строки
• Aho-Corasick, поиск слов из справочного словаря в заданном произвольном тексте

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

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

Эта проблема обсуждается в Hacking a Google Interview Practice Questions - Person 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;
}

Типичный алгоритм будет следующим, со строковыми индексами в диапазоне от 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 вперед в следующей итерации, так как вы знаете, что до этой точки совпадения быть не может. Но, опять же, в этом может не быть необходимости, в зависимости от ваших требований к производительности. Вы должны сами найти баланс между скоростью и ремонтопригодностью.

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

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