C++: Count Occurrences of a Substring


The task is to either create a function, or show a built-in function, to count the number of non-overlapping occurrences of a substring inside a string.
The function should take two arguments: the first argument being the string to search and the second a substring to be searched for.
It should return an integer count.

print countSubstring("the three truths","th")
// do not count substrings that overlap with previously-counted substrings:
print countSubstring("ababababab","abab")

The matching should yield the highest number of non-overlapping matches. In general, this essentially means matching from left-to-right or right-to-left (see proof on talk page).

#include <iostream>
#include <string>

// returns count of non-overlapping occurrences of 'sub' in 'str'
int countSubstring(const std::string& str, const std::string& sub)
	if (sub.length() == 0) return 0;
	int count = 0;
	for (size_t offset = str.find(sub); offset != std::string::npos;
	offset = str.find(sub, offset + sub.length()))
	return count;

int main()
	std::cout << countSubstring("the three truths", "th")    << '\n';
	std::cout << countSubstring("ababababab", "abab")        << '\n';
	std::cout << countSubstring("abaabba*bbaba*bbab", "a*b") << '\n';

	return 0;


Content is available under GNU Free Documentation License 1.2.