-5

What is the most efficient way to count a number of occurrences of a substring in another string in C++? For example, I have a very huge string like

"GQWHIWQGHWGGEEEGQIHIGWHIQWGHIEEEGPHIQPIWGHQPWGPHEEEGQIHWPWGQHPQWGEEE"

and I want to count how often "EEE" occurs.

I could go step by step in a for loop and check every letter if it's an E and if so, count them and if there are 3 es, increment a counter, but I guess there is a more efficient way of doing this.

Maybe a string function? I just wasn't able to find or google a suitable one.

I am searching for a clean C++11 solution.

Anton Savin
  • 40,838
  • 8
  • 54
  • 90
Alex
  • 11
  • 5
  • http://stackoverflow.com/questions/541954/how-would-you-count-occurrences-of-a-string-within-a-string – user7610 Apr 14 '15 at 21:50
  • The referenced question is about C#, not C++. – Sean Bright Apr 14 '15 at 21:51
  • its not a dublicate, the question you postet is a c# question, i want a c++ solution. You cannot compare a c# solution wirh a c++ solution. – Alex Apr 14 '15 at 21:52
  • Also a C solution is not a c++ solution – Alex Apr 14 '15 at 21:52
  • 3
    Sure it is. The referenced question and answer discuss generic searching algorithms. They can be implemented in C++. – Sean Bright Apr 14 '15 at 21:53
  • What about count function from STL http://www.cplusplus.com/reference/algorithm/count/ ? – user7610 Apr 14 '15 at 21:54
  • @Alex - What you are looking for is an algorithm that searches the string the fastest. If you took the time to actually read the link I gave, it gives you the algorithms used to search strings. Having said that, any C++ implementation will practically mimic, if not outright duplicate the same code the C solution gives. There aren't that many different ways to write a Boyer-Moore (for example) search. One thing that you can copy directly from C are *algorithmic approaches*. This is an example where looking at C code to implement something in C++ won't kill your program or design. – PaulMcKenzie Apr 14 '15 at 21:55
  • // count algorithm example #include // std::cout #include // std::count #include // std::vector #include int main ( ) { // counting elements in array: std::string test ( "iqwhhigpÉEEpgihfqwhgwqEEEgjowqogwqoEEEgwqojügwjqojoEEE" ); int mycount = std::count ( test.begin(), test.end(), "EEE" ); std::cout << "10 appears " << mycount << " times.\n"; std::cout << "EEE appears " << mycount << " times.\n"; system ( "pause" ); return 0; } Where is the mistake in the count function? Throws error: – Alex Apr 14 '15 at 22:01
  • error C2446: '==': Keine Konvertierung von 'const char *' in 'int' – Alex Apr 14 '15 at 22:01
  • There is a solution at RosetaCode http://rosettacode.org/wiki/Count_occurrences_of_a_substring#C.2B.2B – user7610 Apr 14 '15 at 22:02
  • http://www.geeksforgeeks.org/pattern-searching-set-7-boyer-moore-algorithm-bad-character-heuristic/ Booyer seems to be the wrong thing if i do not understand it wrong. I want to find out how often a string exists in another string, not where one @zser7610 Year, this solution looks pretty nice, but i am not sure about the performance of using str.find – Alex Apr 14 '15 at 22:05
  • @Alex Your program does not work because std::count counts occurrences of an individual container element in a container. So it can be used to count characters in a string, not substrings in a string. I was wrong to suggest it. – user7610 Apr 14 '15 at 22:05
  • @Alex - Look at the link you posted -- it starts out with a program that prints all occurrences. Come on, how hard would it be to take that code at RosetaCode and change it to just stick a counter variable that increments every time a string is found? – PaulMcKenzie Apr 14 '15 at 22:09
  • @Alex Look at the `offset` variable. It goes through the string only once. Therefore it is linear in the length of the string searched in. (And the string searched for). O(m+n) If you are ok with "non-overlapping occurrences", then the RosetaCode solution is the best you can get. – user7610 Apr 14 '15 at 22:10
  • Reasonable overview of existing string search algorithms is on WIkipedia, #Finite_state_automaton_based_search – user7610 Apr 14 '15 at 22:10
  • How many times does "eee" exist in "eeee"? Once, or twice? –  Apr 14 '15 at 22:22

1 Answers1

0

Well, if you want a fast and efficent solution, take a look at Knuth–Morris–Pratt algorithm - it takes only O(N+M) to search. If you want something in STL style, then take a look at std::string::find

Chan Kha Vu
  • 9,834
  • 6
  • 32
  • 64