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

Опубликовано: 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 и т. Д.
Пожалуйста, обратитесь к полной статье о проверке, является ли строка подстрокой другой для получения более подробной информации!

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