Поиск по наивному шаблону - это метод поиска в строке определенного шаблона или подстроки. Это делается путем проверки всех символов строки на наличие шаблона. В этой статье мы исследуем способ реализации этого с помощью JavaScript.
Допустим, мы хотели узнать, сколько раз шаблон встречается в строке. Тогда наша функция должна будет принять два аргумента: строку, которую мы будем искать, и строку, состоящую из шаблона, который мы хотели бы найти в нашей основной строке. Переменная, которая будет нашим счетчиком, также должна быть определена в начале нашей функции.
Мы начинаем с итерации по нашей первой строке, а в этом цикле мы будем перебирать нашу вторую строку (шаблон).
Целью второго цикла for является перебор нашего шаблона и сравнение буквы за буквой, чтобы увидеть, совпадает ли он со строкой. Начнем с первого символа нашей строки. Если он соответствует первому символу нашего шаблона, мы продолжаем работу. Идея состоит в том, чтобы продолжать проверку, пока не будут выполнены два условия:
- Символы не совпадают, и нам придется выйти из цикла и перейти к следующему символу нашей строки (поскольку символы не совпадают, эта итерация не приведет к созданию экземпляра нашего шаблона).
- Мы достигли длины нашего шаблона и, таким образом, все символы совпадают, и мы нашли экземпляр шаблона в строке. В этом случае мы увеличим наш счетчик.
Вот как будет выглядеть эта логика:
Отсюда мы можем просто вернуть счетчик в конце функции, дав нам количество экземпляров, которые шаблон появляется в нашей строке.
Временная сложность этой функции составляет O (n * m), где n - длина строки, а m - длина строки шаблон. Кроме того, эта функция предполагает, что длина шаблона меньше длины строки. Если мы хотим проверить крайние случаи, нам нужно будет убедиться, что длина шаблона действительно меньше, чем длина строки в начале нашей функции.
