(Реализация Javascript)
Временная сложность:
Худший случай: O (m * n)
Как это работает:
Мы собираемся создать функцию с параметром для givenString и параметром для шаблона, который мы ищем.
Сначала давайте создадим счетчик, чтобы подсчитать, сколько совпадений мы находим.
Затем, чтобы сравнить две строки, нам нужно создать цикл, который позаботится обо всех индексах givenString, а также внутренний цикл для сравнения индексов.
Пока мы находимся в индексе 0 внешнего цикла, внутренний цикл проверяет, равны ли элементы, содержащиеся в индексе 0 givenString и pattern. Если есть совпадение, внутренний цикл переместится на один индекс вперед и сравнит следующий элемент pattern с индексом +1 givenString.
Он будет делать это до тех пор, пока не найдет совпадение по шаблону, а затем добавит +1 к счетчику.
Каждый раз, когда внутренний цикл не находит совпадения, он прерывается, поэтому внешний цикл может переместиться на один индекс вперед, позволяя нам перемещаться по всей givenString.
Учтите, что это метод грубой силы с вложенными циклами. На это уходит очень много времени.
Давайте посмотрим на изображения, чтобы лучше понять, что происходит.
Псевдокод
// Define a function that takes 2 strings. The large one and the pattern we're looking for. // Loop over the longer string. // Loop over the shorter string. // If the characters don't match, break out of the inner loop. // If the characters do match, keep going. // If you complete the inner loop and find a match, increment the count of matches. // Return the count
