kmp-algorithm-google_code_style.cpp

#include <iostream>
#include <string>
#include <vector>
class KMPSearcher {
 public:
  explicit KMPSearcher(const std::string &pattern) : pattern_(pattern) {
    FiilPi();
  }
  template <class Callback>
  void Search(const std::string &text, Callback on_occurence) const {
    size_t prev = 0;
    for (int i = 0; i < text.size(); ++i) {
      while ((prev > 0) && (pattern_[prev] != text[i])) {
        prev = pi_[prev - 1];
      }
      if (text[i] == pattern_[prev]) {
        ++prev;
      }
      if (prev == pattern_.size() - 1) {
        on_occurence(i - prev + 1);
      }
    }
  }

 private:
  void FiilPi() {
    pi_.push_back(0);
    for (int i = 1; i < pattern_.size(); ++i) {
      int candidate = pi_[i - 1];
      while ((candidate > 0) && (pattern_[candidate] != pattern_[i])) {
        candidate = pi_[candidate - 1];
      }
      if (pattern_[i] == pattern_[candidate]) {
        ++candidate;
      }
      pi_.push_back(candidate);
    }
  }
  const std::string &pattern_;
  std::vector<size_t> pi_;
};

int main() {
  std::string pattern;
  std::string text;
  std::cin >> pattern >> text;
  pattern += '#';
  KMPSearcher main_pattern(pattern);
  main_pattern.Search(text, [&](size_t left) { std::cout << left << " "; });
  return 0;
}