Программа Python для проверки того, является ли строка подстрокой другой

Опубликовано: 20 Сентября, 2022

Имея две строки s1 и s2, найдите, является ли s1 подстрокой строки s2. Если да, верните индекс первого вхождения, иначе верните -1.

Примеры :

Input: s1 = "for", s2 = "geeksforgeeks"
Output: 5
Explanation:
String "for" is present as a substring
of s2.

Input: s1 = "practice", s2 = "geeksforgeeks"
Output: -1.
Explanation:
There is no occurrence of "practice" in
"geeksforgeeks"

Простой подход: идея состоит в том, чтобы запустить цикл от начала до конца и для каждого индекса в заданной строке проверить, может ли подстрока быть сформирована из этого индекса. Это можно сделать, запустив вложенный цикл, проходящий по заданной строке, и в этом цикле запустите еще один цикл, проверяющий подстроку из каждого индекса.
Например, предположим, что есть строка длины N и подстрока длины M. Затем запустите вложенный цикл, где внешний цикл проходит от 0 до (NM), а внутренний цикл — от 0 до M. Для самого индекса проверьте, подстрока, пройденная внутренним циклом, является заданной подстрокой или нет.

Выход:

Present at index 5

Анализ сложности:

  • Временная сложность: O(m * n), где m и n — длины s1 и s2 соответственно.
    Используется вложенный цикл, внешний цикл выполняется от 0 до NM, а внутренний цикл — от 0 до M, поэтому сложность равна O(m*n).
  • Космическая сложность: O(1).
    Так как не требуется дополнительное место.

Эффективным решением является использование алгоритма поиска O(n), такого как алгоритм KMP, алгоритм Z и т. д.
Языковые реализации:

  • Подстрока Java
  • подстрока в С++
  • питон найти

Еще одно эффективное решение:

  • Для эффективного решения потребуется только один обход, т.е. O(n) на более длинной строке s1. Здесь мы начнем обход строки s1 и будем поддерживать указатель на строку s2 с 0-го индекса.
  • Для каждой итерации мы сравниваем текущий символ в s1 и сверяем его с указателем в s2.
  • Если они совпадают, мы увеличиваем указатель на s2 на 1. И для каждого несоответствия мы устанавливаем указатель обратно на 0.
  • Также держим проверку, когда значение указателя s2 равно длине строки s2, если true, мы ломаем и возвращаем значение (указатель строки s1 — указатель строки s2)
  • Работает со строками, содержащими повторяющиеся символы.

Выход:

18

Анализ сложности:

Сложность приведенного выше кода будет по-прежнему O (n * m) в худшем случае, а пространственная сложность - O (1).

Пожалуйста, обратитесь к полной статье о проверке, является ли строка подстрокой другой для получения более подробной информации!

РЕКОМЕНДУЕМЫЕ СТАТЬИ