Подсчет вхождений подстроки X перед каждым вхождением подстроки Y в данной строке

Даны три строки S , X и Y , состоящие из N , A и B символов соответственно, задача состоит в том, чтобы найти количество вхождений подстроки X перед каждым вхождением подстроки Y в данной строке S .

Примеры:

Input S = ”abcdefdefabc”, X = ”def”, Y = ”abc”
Output: 0 2
Explanation:
First occurrence of Y(= “abc”): No of occurrences of X(= “def”) = 0.
Second occurrence of Y: No of occurrences of X = 0.

Input: S = ”accccbbbbbbaaa”, X = ”a”, Y = ”b”
Output: 0 6 6 6

Подход: выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, count , которая хранит общее количество вхождений X.
• Пройдите по заданной строке S и выполните следующие шаги:
  • Если подстрока в диапазоне [i, B] равна Y , тогда счетчик увеличивается на 1 .
  • Если подстрока в диапазоне [i, A] равна X , тогда выведите значение count как результирующее количество строки Y перед текущим вхождением строки X .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*(A + B)), так как мы используем цикл для прохождения N раз и используем встроенную функцию подстроки, которая будет стоить нам O(A+B) времени.
Вспомогательное пространство: O(1), так как мы не используем дополнительное пространство.