#include <string>
#include <vector>
using namespace std;

class HashPatternSearcher {
private:
  string _pat, _txt;
  const int _ALPHABET_SIZE = 'Z' - 'A' + 1;
  long long _mod; char _initChar;
  vector<long long> _powVec, _hashBaseText;
  long long _hashBasePat;
  void buildHashBase(const bool rebuildHashPatBase = false) {
    long txtLen = (this->_txt).length();
    (this->_powVec).push_back(1);
    for (long i = 1; i <= txtLen; ++i) (this->_powVec).push_back(((this->_powVec).at(i-1) * this->_ALPHABET_SIZE) % this->_mod);
    (this->_hashBaseText).push_back(0);
    for (long i = 1; i <= txtLen; ++i) (this->_hashBaseText).push_back(((this->_hashBaseText).at(i-1) * this->_ALPHABET_SIZE + (this->_txt).at(i-1) - this->_initChar) % this->_mod);
    if (!rebuildHashPatBase) return;
    long patLen = (this->_pat).length();
    this->_hashBasePat = 0;
    for (long i = 1; i <= patLen; ++i) this->_hashBasePat = (this->_hashBasePat * this->_ALPHABET_SIZE + (this->_pat).at(i-1) - this->_initChar) % this->_mod;
  };
public:
  HashPatternSearcher(const string pattern, const string text = string(), const char initCharacter = 'a', const long long modulo = ((long long)1<<(long long)31)-(long long)1) {
    this->_pat = pattern;
    this->_txt = text;
    this->_initChar = initCharacter;
    this->_mod = modulo;
    this->buildHashBase(true);
  };
  void resetText(const string text = string()) {
    this->_txt = text;
    this->buildHashBase();
  };
  void resetInitChar(const char initCharacter = 'a', const bool rebuildHashBase = true) {
    this->_initChar = 'a';
    if (rebuildHashBase) buildHashBase(true);
  };
  void resetModulo(const long long modulo = ((long long)1<<(long long)31)-(long long)1, const bool rebuildHashBase = true) {
    this->_mod = modulo;
    if (rebuildHashBase) buildHashBase(true);
  };
  long long getTextHash(long start, long end) {
    ++start, ++end;
    return ((this->_hashBaseText).at(end) - (this->_hashBaseText).at(start-1) * (this->_powVec).at(end-start+1) + this->_mod * this->_mod) % this->_mod;
  };
  long long getPatternHash() {
    return this->_hashBasePat;
  };
  vector<long> getOccurrences() {
    vector<long> res;
    long txtLen = (this->_txt).length();
    long patLen = (this->_pat).length();
    long limit = txtLen-patLen+1;
    for (long i = 0; i < limit; ++i) if (this->getTextHash(i, i+patLen-1) == this->_hashBasePat) res.push_back(i);
    return res;
  };
  long getOccurrences(vector<long>& vec) {
    return (vec = this->getOccurrences()).size();
  };
};