Cod sursa(job #2725688)

Utilizator avtobusAvtobus avtobus Data 19 martie 2021 15:31:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
// const int INF = 0x3f3f3f3f;
const int p = 73;
const int mod1 = 100'007;
const int mod2 = 100'021;

ifstream fin {"strmatch.in"};
ofstream fout {"strmatch.out"};

int main(void) {
  // freopen("strmatch.in", "r", stdin);
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);

  string A, B;
  fin >> A >> B;
  int N = A.size(), M = B.size();

  if (N > M) {
    fout << "0\n";
    return 0;
  }

  int ha1 = 0, ha2 = 0, hb1 = 0, hb2 = 0;
  int p1 = 1, p2 = 1;
  for(int i = 0; i < N; i++) {
    ha1 = (ha1 * p + A[i]) % mod1;
    ha2 = (ha2 * p + A[i]) % mod2;

    hb1 = (hb1 * p + B[i]) % mod1;
    hb2 = (hb2 * p + B[i]) % mod2;

    p1 = (p1 * p) % mod1;
    p2 = (p2 * p) % mod2;
  }

  vi res {};
  int ans = 0;
  if (ha1 == hb1 && ha2 == hb2) {
    ans ++;
    res.push_back(0);
  }
  for(int i = N; i < M; i++) {
    hb1 = (hb1 * p + B[i]) % mod1 - (B[i-N] * p1) % mod1;
    hb1 += (hb1 < 0 ? mod1 : 0);

    hb2 = (hb2 * p + B[i]) % mod2 - (B[i-N] * p2) % mod2;
    hb2 += (hb2 < 0 ? mod2 : 0);

    if (ha1 == hb1 && ha2 == hb2) {
      ans++;
      if (ans <= 1000)
        res.push_back(i-N+1);
    }
  }

  fout << ans << '\n';
  for(auto x: res)
    fout << x << ' ';
  fout << '\n';

  return 0;
}