Строка поиска для последовательности строк

Question

Каков наиболее эффективный способ подсчета числа вхождений подстроки в другую строку на C++? Например, у меня есть очень большая строка, как

"GQWHIWQGHWGGEEEGQIHIGWHIQWGHIEEEGPHIQPIWGHQPWGPHEEEGQIHWPWGQHPQWGEEE" 

и я хочу, чтобы подсчитать, как часто "EEE" происходит.

Я мог бы пойти шаг за шагом в цикл for и проверить каждую букву, если это E, и если да, посчитайте их, и если есть 3 e s, увеличьте счетчик, но я думаю, что существует более эффективный способ делая это.

Может быть, функция строки? Я просто не смог найти или сделать подходящий.

Я ищу чистое решение на C++ 11.

Answer 1

Ну, если вы хотите быстрое и эффективное решение, взгляните на Knuth–Morris–Pratt algorithm - для поиска требуется только O (N + M). Если вы хотите что-то в стиле STL, то посмотрите на std::string::find