Rolling Hash to find pattern in a String

// I can't tell you what it really is,
// I can only tell you what it feels like.
#include "bits/stdc++.h"
using namespace std;

#define int long long
#define F first
#define S second
#define sz(x) ((int)x.size())
#define rep(i,a,n) for (int i = a; i <= n; ++i)
#define all(v)  v.begin(), v.end()
#define pb push_back
#define P pair < int, int >
#define E cout << '\n'

int add(int, int, int);
int mul(int, int, int);
int po(int, int, int);
int sub(int, int, int);

const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
const int p1 = 31;
const int p2 = 37;

const int N = 1e6 + 5;

int pl1[N], pl2[N];

void pre() {
  pl1[0] = 1, pl2[0] = 1;
  for (int i = 1; i < N; ++i) {
    pl2[i] = mul(p2, pl2[i-1], mod2);
    pl1[i] = mul(p1, pl1[i-1], mod1);
  }
}

inline void solve() {
  string text, patt;
  vector < int > v;
  int n, m;
  cin >> text >> patt;
  n = text.size(), m = patt.size();
  if (m > n) {
    cout << "Not Found\n\n";
    return;
  }
  text = '!' + text;
  patt = '!' + patt;

  vector < int > h1(n+1), h2(n+1); // Hash in base p1 and p2;

  for (int i = 1; i <= n; ++i) {
    h1[i] = add(mul(h1[i-1], p1, mod1), text[i] - 'a' + 1, mod1);
    h2[i] = add(mul(h2[i-1], p2, mod2), text[i] - 'a' + 1, mod2);
  }

  int cur1 = 0, cur2 = 0;
  for (int i = 1; i <= m; ++i) {
    cur1 = add(mul(cur1, p1, mod1), patt[i] - 'a' + 1, mod1);
    cur2 = add(mul(cur2, p2, mod2), patt[i] - 'a' + 1, mod2);
  }

  auto find = [&] (int l, int r) {
    if (l == 1) {
      return make_pair(h1[r], h2[r]);
    }
    int x = sub(h1[r], mul(h1[l-1], pl1[r-l+1], mod1), mod1);
    int y = sub(h2[r], mul(h2[l-1], pl2[r-l+1], mod2), mod2);
    return make_pair(x, y);
  };
  pair < int, int > p = make_pair(cur1, cur2);

  for (int i = 1; i + m - 1 <= n; ++i) {
    if (p == find(i, i+m-1)) {
      v.push_back(i);
    }
  }

  if (!v.empty()) {
    cout << v.size() << '\n';
    for (int x : v) {
      cout << x << ' ';
    }
    cout << "\n\n";
  }
  else {
    cout << "Not Found\n\n";
    return;
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  int t = 1;
  pre();
  cin >> t; while(t--)
  solve();
  return 0;
}
inline int add(int x, int y, int mod) {
   if (x >= mod) x %= mod;
   if (y >= mod) y %= mod;
   x  += y;
   return (x >= mod ? x - mod : x);
}
inline int mul(int x, int y, int mod) {
  if (x >= mod) x %= mod;
  if (y >= mod) y %= mod;
  return (x*y) % mod;
}
inline int sub(int x, int y, int mod) {
  return ((x-y)%mod+mod) % mod;
}
int po(int x, int n, int mod) {
  int res = 1;
  for (;n > 0;) {
    if (n & 1) {
      res = mul(res, x, mod);
    }
    x = mul(x, x, mod);
    n /= 2;
  }
  return res;
}