fork(4) download
copy 
  1. #include <string>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. class kmp {
  8. 	string& sample;
  9. 	vector<size_t> prefix;
  10. 	int last_prefix;
  11. public:
  12. 	kmp(string& sample) :sample(sample), prefix(sample.length()) {
  13. 		last_prefix = prefix[0] = 0;
  14. 		for (size_t i=1; i<sample.length(); i++) {
  15. 			next(sample[i]);
  16. 			prefix[i] = last_prefix;
  17. 		}
  18. 		reset();
  19. 	}
  20.  
  21. 	bool next(char c) {
  22. 		while (last_prefix > 0 && sample[last_prefix] != c)
  23. 			last_prefix = prefix[last_prefix-1];
  24.  
  25. 		if (sample[last_prefix] == c)
  26. 			last_prefix++;
  27.  
  28. 		return last_prefix == sample.length();
  29. 	}
  30.  
  31. 	void reset()  {
  32. 		last_prefix = 0;
  33. 	}
  34. };
  35.  
  36. int main() {
  37. 	string sample = "aabaa";
  38. 	string text = "aabaabaaaabaabaaab";
  39.  
  40. 	kmp matcher(sample);
  41.  
  42. 	for (size_t i=0; i<text.length(); i++) {
  43. 		if (matcher.next(text[i])) {
  44. 			cout << i + 1 - sample.length() << endl;
  45. 		}
  46. 	}
  47. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
3
8
11
https://ideone.com/zn9Fe4
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!