Cod sursa(job #3340625)

Utilizator Gerald123Ursan George Gerald123 Data 15 februarie 2026 14:34:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
/// patratele
#include <bits/stdc++.h>
using namespace std;

#define MOD1 100021
#define MOD2 100007
#define Baza 97
#define NMAX 2000005

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

long long i, la, lb, hasha1, hasha2, hashb1, hashb2, ras[NMAX], vf, p1, p2;
char a[NMAX], b[NMAX];

int main()
{
  // ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  fin >> a >> b;
  la = strlen(a);
  lb = strlen(b);
  p1=p2=1;
  for (i = 0; i < la; i++)
  {
    hasha1 = (hasha1 * Baza % MOD1 + a[i])%MOD1;
    hasha2 = (hasha2 * Baza % MOD2 + a[i])%MOD2;

    hashb1 = (hashb1 * Baza % MOD1 + b[i])%MOD1;
    hashb2 = (hashb2 * Baza % MOD2 + b[i])%MOD2;

    if (i != 0)
    {
      p1 = p1 * Baza % MOD1;
      p2 = p2 * Baza % MOD2;
    }
  }

  if (hasha1 == hashb1 && hasha2 == hashb2)
    ras[++vf] = 0;
  for (i = la; i < lb; i++)
  {
    hashb1 = ((hashb1 + MOD1 - (p1 * b[i - la] % MOD1))%MOD1 * Baza % MOD1 + b[i]) % MOD1;
    hashb2 = ((hashb2 + MOD2 - (p2 * b[i - la] % MOD2))%MOD2 * Baza % MOD2 + b[i]) % MOD2;

    if (hasha1 == hashb1 && hasha2 == hashb2)
      ras[++vf] = i - la + 1;
  }
  fout << vf << '\n';
  for (i = 1; i <= min(vf, 1000ll); i++)
    fout << ras[i] << " ";
  return 0;
}