Поиск первого вхождение подстроки. Решение в лоб.

Поиск информации — одно из основных использований компьютера. Одна из простейших задач поиска информации — поиск точно заданной подстроки в строке. Тем не менее, эта задача чрезвычайно важна — она применяется в текстовых редакторах, СУБД, поисковых машинах…


С поиском подстроки мы встречаемся постоянно. Всем любимый ctrl+f, это именно то, что нам нужно.
Часто ли вы задумывались, а как оно работает? Многие из Вас, наверняка, скажут, что если потребуется - сделаем.
Большинство, думаю, решат эту задачу в лоб и для наглядности я покажу, как это сделать.

Прямой поиск, или, как еще часто говорят, «просто взять и поискать» - это первое решение, которое приходит в голову неискушенному программисту. Суть проста: идти по проверяемой строке A и искать в ней вхождение первого символа искомой строки X. Когда находим, делаем гипотезу, что это и есть то самое искомое вхождение. Затем остается проверять по очереди все последующие символы шаблона на совпадение с соответствующими символами строки A. Если они все совпали — значит вот оно, прямо перед нами. Но вот если какой-то из символов не совпал, то ничего не остается, как признать нашу гипотезу неверной, что возвращает нас к символу, следующему за вхождением первого символа из X.

Многие люди ошибаются в этом пункте, считая, что не надо возвращаться назад, а можно продолжать обработку строки A с текущей позиции. Почему это не так, легко продемонстрировать на примере поиска X=«AAAB» в A=«AAAAB». Первая гипотеза нас приведет к четвертому символу A: "AAAAB", где мы обнаружим несоответствие. Если не откатиться назад, то вхождение мы так и не обнаружим, хотя оно есть.
Неправильные гипотезы неизбежны, а из-за таких откатываний назад, при плохом стечении обстоятельств, может оказаться, что мы каждый символ в A проверили около |X| раз. То есть вычислительная сложность сложность алгоритма O(|X||A|). Так поиск фразы в параграфе может и затянуться...

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

А вот и реализация:

def stringSearch(s, x):
    i=j=0
    lengthS = len(s)# Длина строки в которой ищем
    lengthX = len(x)# -||- которую ищем
    # пока не достигли одного из концов
    while i<=lengthS - lengthX and j>lengthx:
     # если совпали буквы продвигаемся по обеим строкам
        if li[i+j]==x[j]:
            j+=1
        # иначе двигаемся по строке(+1), начиная с 0 символа подстроки
        else:
            i+=1
            j=0
    # если дошли до конца подстроки - нашли, иначе - нет
    return i if j==lengthX else None

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


Используемая литература:

1. Википедия
2. habrahabr