Language: C++

#include <iostream>
#include <vector>

using namespace std;

// 蟻本でみた、ローリングハッシュを試してみる
vector<bool> check_eq(string s, string t) {
  int s_size = s.size();
  int t_size = t.size();
  vector<bool> result(s_size - t_size + 1);
  // modは2**64だと簡単に衝突する。また、複数用意して衝突しづらくする
  // http://hos.ac/blog/#blog0003 より
  vector<uint64_t> mods{1000000007, 999999937};
  uint64_t b = 10007;
  vector<uint64_t> bns(mods.size(), 1);
  vector<uint64_t> s_hash(mods.size(), 0);
  vector<uint64_t> t_hash(mods.size(), 0);
  int m_size = mods.size();
  
  for (int i = 0; i < t_size; i++) {
    for(int j = 0; j < m_size; j++) {
      const auto& m = mods[j];
      bns[j] = (bns[j] * b) % m;
    }
  }
  
  int i = 0;
  for(; i < t_size; i++) {
    for(int j = 0; j < m_size; j++) {
      const auto& m = mods[j];
      t_hash[j] = ((t_hash[j] * b) % m + t[i]) % m;
      s_hash[j] = ((s_hash[j] * b) % m + s[i]) % m;
    }
  }
  
  for(;;i++) {
    bool current_result = true;
    for(int j = 0; j < m_size; j++) {
      current_result &= s_hash[j] == t_hash[j];
    }

    result[i - t_size] = current_result;
    
    if (i >= s_size) {
      break;
    }

    for(int j = 0; j < m_size; j++) {
      const auto& m = mods[j];
      s_hash[j] = ((s_hash[j] * b) % m + s[i] - s[i - t_size] * bns[j]) % m;
    }
  }
  
  return result;
}

int main() {
  string s,t,s_origin;
  cin >> s >> t;
  s_origin = s;
  
  while(s.size() < t.size()+s_origin.size()) {
    s += s_origin;
  }
  
  vector<bool> eqs = check_eq(s,t);
  
  int s_origin_size = s_origin.size();
  int t_size = t.size();

  for (int i = 0; i < s_origin_size; i++) {
    if (eqs[i] && (s.substr(i, t_size) != t)) {
      cout << s_origin << " " << s << " " << t << " " << i << " " << (s.substr(i, t_size)) << " " << t << " " << eqs[i] << endl;
      throw 1;
    }
  }
  
  return 0;
}


Compiler output:
a.cc: In function 'std::vector<bool> check_eq(std::string, std::string)':
a.cc:13:10: error: 'uint64_t' was not declared in this scope
   13 |   vector<uint64_t> mods{1000000007, 999999937};
      |          ^~~~~~~~
a.cc:3:1: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
    2 | #include <vector>
  +++ |+#include <cstdint>
    3 | 
a.cc:13:18: error: template argument 1 is invalid
   13 |   vector<uint64_t> mods{1000000007, 999999937};
      |                  ^
a.cc:13:18: error: template argument 2 is invalid
a.cc:13:20: error: scalar object 'mods' requires one element in initializer
   13 |   vector<uint64_t> mods{1000000007, 999999937};
      |                    ^~~~
a.cc:14:11: error: expected ';' before 'b'
   14 |   uint64_t b = 10007;
      |           ^~
      |           ;
a.cc:15:18: error: template argument 2 is invalid
   15 |   vector<uint64_t> bns(mods.size(), 1);
      |                  ^
a.cc:15:38: error: expression list treated as compound expression in initializer [-fpermissive]
   15 |   vector<uint64_t> bns(mods.size(), 1);
      |                                      ^
a.cc:16:18: error: template argument 2 is invalid
   16 |   vector<uint64_t> s_hash(mods.size(), 0);
      |                  ^
a.cc:16:41: error: expression list treated as compound expression in initializer [-fpermissive]
   16 |   vector<uint64_t> s_hash(mods.size(), 0);
      |                                         ^
a.cc:17:18: error: template argument 2 is invalid
   17 |   vector<uint64_t> t_hash(mods.size(), 0);
      |                  ^
a.cc:17:41: error: expression list treated as compound expression in initializer [-fpermissive]
   17 |   vector<uint64_t> t_hash(mods.size(), 0);
      |                                         ^
a.cc:23:10: error: invalid types 'int[int]' for array subscript
   23 |       bns[j] = (bns[j] * b) % m;
      |          ^
a.cc:23:20: error: invalid types 'int[int]' for array subscript
   23 |       bns[j] = (bns[j] * b) % m;
      |                    ^
a.cc:23:26: error: 'b' was not declared in this scope
   23 |       bns[j] = (bns[j] * b) % m;
      |                          ^
a.cc:31:13: error: invalid types 'int[int]' for array subscript
   31 |       t_hash[j] = ((t_hash[j] * b) % m + t[i]) % m;
      |             ^
a.cc:31:27: error: invalid types 'int[int]' for array subscript
   31 |       t_hash[j] = ((t_hash[j] * b) % m + t[i]) % m;
      |                           ^
a.cc:31:33: error: 'b' was not declared in this scope
   31 |       t_hash[j] = ((t_hash[j] * b) % m + t[i]) % m;
      |                                 ^
a.cc:32:13: error: invalid types 'int[int]' for array subscript
   32 |       s_hash[j] = ((s_hash[j] * b) % m + s[i]) % m;
      |             ^
a.cc:32:27: error: invalid types 'int[int]' for array subscript
   32 |       s_hash[j] = ((s_hash[j] * b) % m + s[i]) % m;
      |                           ^
a.cc:39:31: error: invalid types 'int[int]' for array subscript
   39 |       current_result &= s_hash[j] == t_hash[j];
      |                               ^
a.cc:39:44: error: invalid types 'int[int]' for array subscript
   39 |       current_result &= s_hash[j] == t_hash[j];
      |                                            ^
a.cc:50:13: error: invalid types 'int[int]' for array subscript
   50 |       s_hash[j] = ((s_hash[j] * b) % m + s[i] - s[i - t_size] * bns[j]) % m;
      |             ^
a.cc:50:27: error: invalid types 'int[int]' for array subscript
   50 |       s_hash[j] = ((s_hash[j] * b) % m + s[i] - s[i - t_size] * bns[j]) % m;
      |                           ^
a.cc:50:33: error: 'b' was not declared in this scope
   50 |       s_hash[j] = ((s_hash[j] * b) % m + s[i] - s[i - t_size] * bns[j]) % m;
      |                                 ^
a.cc:50:68: error: invalid types 'int[int]' for array subscript
   50 |       s_hash[j] = ((s_hash[j] * b) % m + s[i] - s[i - t_size] * bns[j]) % m;
      |                                                                    ^