fork(3) download
  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
stdin
Standard input is empty
stdout
0
3
8
11