Open IllidanSR opened 2 years ago
У этой задачи слишком много возможных решений с разными трейдоффами, чтобы дать Единственно Правильное. Если длина строки n
, длина паттерна m
, например:
O(1)
, время O(n*m)
O(m)
, время O(n+m)
O(n+m)
, время O(n+m)
O(n+m)
, время O(n+m)
Если сделать простой перебор, то это мало кому понравится. А в "быстрых" алгоритмах надо откуда-то взять память.
+ непонятно, считать ли за "вхождение" перекрывающиеся строки, т.е.
"ababa".count("aba"); // вернет 1 или 2?
Часто бывает нужно проверить есть ли в строке определённая подстрока, вернув количество вхождений. Во многих языках для строк существует метод
.count(patter)
возвращающий количество вхождений подстроки в строке. В C++ есть std::count, но он работает только с char в качестве паттерна, что выглядит не совсем подходящим. Предложение: добавить в класс string метод count принимающий в качестве аргумента паттерн поиска и возвращающий количество вхождений паттерна в строку