Cod sursa(job #1982189)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 17 mai 2017 21:03:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;
const int MOD1 = 100003;
const int MOD2 = 100043;
const int MAXL = 2000010;
const int ORI = 73;
char s1[MAXL], s2[MAXL], pot[MAXL];
int main()
{
  FILE *fin, *fout;
  int n1, n2, hh1, hh2, p1, p2, i, h1, h2, nr;
  fin = fopen ("strmatch.in", "r");
  fout = fopen ("strmatch.out", "w");
  fscanf (fin, "%s", &s1);
  n1 = strlen (s1);
  fscanf (fin, "%s", &s2);
  n2 = strlen (s2);
  hh1 = hh2 = 0;
  p1 = p2 = 1;
  for (i = 0; i < n1; i++) {
    hh1 = (hh1 * ORI + s1[i] - '0') % MOD1;
    hh2 = (hh2 * ORI + s1[i] - '0') % MOD2;
    if (i > 0) {
      p1 = (p1 * ORI) % MOD1;
      p2 = (p2 * ORI) % MOD2;
    }
  }
  h1 = h2 = 0;
  for (i = 0; i < n1; i++) {
    h1 = (h1 * ORI + s2[i] - '0') % MOD1,
    h2 = (h2 * ORI + s2[i] - '0') % MOD2;
  }
  nr = 0;
  if (hh1 == h1 && hh2 == h2) {
    pot[0] = 1;
    nr++;
  }
  for (i = n1; i < n2; i++) {
    h1 = ((h1 - ((s2[i - n1] - '0') * p1) % MOD1 + MOD1) * ORI + s2[i] - '0') % MOD1;
    h2 = ((h2 - ((s2[i - n1] - '0') * p2) % MOD2 + MOD2) * ORI + s2[i] - '0') % MOD2;
    if (h1 == hh1 && h2 == hh2) {
      pot[ i - n1 + 1 ] = 1;
      nr++;
    }
  }
  fprintf (fout, "%d\n", nr);
  for (i = 0; i < n2; i++)
    if (pot[i] == 1)
      fprintf (fout, "%d ", i);
  fclose (fin);
  fclose (fout);
  return 0;
}