fork download
  1. #include <string>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. template<typename A> void kmp(string const& sample, string const& text, A const& action) {
  8. vector<size_t> prefix(sample.length());
  9.  
  10. size_t last_prefix = prefix[0] = 0;
  11. for (size_t i=1; i<sample.length(); i++) {
  12. while (last_prefix > 0 && sample[last_prefix] != sample[i])
  13. last_prefix = prefix[last_prefix-1];
  14.  
  15. if (sample[last_prefix] == sample[i])
  16. last_prefix++;
  17.  
  18. prefix[i] = last_prefix;
  19. }
  20.  
  21. last_prefix = 0;
  22. for (size_t i=0; i<text.length(); i++) {
  23. while (last_prefix > 0 && sample[last_prefix] != text[i])
  24. last_prefix = prefix[last_prefix-1];
  25.  
  26. if (sample[last_prefix] == text[i])
  27. last_prefix++;
  28.  
  29. if (last_prefix == sample.length()) {
  30. action(i + 1 - sample.length());
  31. }
  32. }
  33. }
  34.  
  35. int main() {
  36. string sample = "aabaa";
  37. string text = "aabaabaaaabaabaaab";
  38.  
  39. kmp(sample, text, [&](size_t i){
  40. cout << i << endl;
  41. });
  42. }
Success #stdin #stdout 0s 3460KB
stdin
Standard input is empty
stdout
0
3
8
11