Добавить для std::string метод count()

[IllidanSR]

Часто бывает нужно проверить есть ли в строке определённая подстрока, вернув количество вхождений. Во многих языках для строк существует метод .count(patter) возвращающий количество вхождений подстроки в строке. В C++ есть std::count, но он работает только с char в качестве паттерна, что выглядит не совсем подходящим. Предложение: добавить в класс string метод count принимающий в качестве аргумента паттерн поиска и возвращающий количество вхождений паттерна в строку

[Izaron]

У этой задачи слишком много возможных решений с разными трейдоффами, чтобы дать Единственно Правильное. Если длина строки n, длина паттерна m, например:

• простой перебор, память O(1), время O(n*m)
• алгоритм Рабина-Карпа, память вроде бы O(m), время O(n+m)
• z-функция, память O(n+m), время O(n+m)
• префикс-функция, память O(n+m), время O(n+m)

Если сделать простой перебор, то это мало кому понравится. А в "быстрых" алгоритмах надо откуда-то взять память.

+ непонятно, считать ли за "вхождение" перекрывающиеся строки, т.е.

"ababa".count("aba"); // вернет 1 или 2?