Cod sursa(job #3161255)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 26 octombrie 2023 10:49:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.08 kb
#include <iostream>
#include <fstream>

#define MOD1 666013
#define MOD2 1000003
#define BASE 62
#define MAXL 2000000
#define MAXP 1000

using namespace std;

int app[MAXP], dr = 0;
char str[MAXL];

//012345678910111213141516171819202122232425262728293031323334353637383940414243445464748494505152535455565758596061
//0123456789 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z

char getVal(char c){
  if(c >= '0' && c <= '9')
    return c - '0';
  if(c >= 'A' && c <= 'Z')
    return c - 'A' + 10;
  return c - 'a' + 36;
}

int main(){
  char c;
  long long s1, s2, l, i, p1, p2, n;
  FILE *fin, *fout;

  fin = fopen("strmatch.in", "r");
  c = fgetc(fin);
  s1 = 0;
  s2 = 0;
  l = 0;

  while(c != '\n'){
    s1 *= BASE;
    s1 += getVal(c);
    s1 %= MOD1;

    s2 *= BASE;
    s2 += getVal(c);
    s2 %= MOD2;
    
    l ++;
    c = fgetc(fin);
  }

  p1 = p2 = 1;
  for(i = 0; i < l - 1; i ++){ // Calculam valoarea celei mai semnificative cifre pentru ambele modulo
    p1 *= BASE;
    p1 %= MOD1;

    p2 *= BASE;
    p2 %= MOD2;
  }

  c = fgetc(fin);
  n = 0;
  while(c != '\n'){
    str[n ++] = getVal(c);
    c = fgetc(fin);
  }
  fclose(fin);

  // printf("%d: %d %d,  %d %d\n", l, s1, s2, p1, p2);
  
  int x1 = 0, x2 = 0;
  for(i = 0; i < l; i ++){
    x1 *= BASE;
    x1 += str[i]; 
    x1 %= MOD1;

    x2 *= BASE;
    x2 += str[i];
    x2 %= MOD2;
  }
  while(i < n){
    // printf("x1 = %d, x2 = %d\n", x1, x2);
    if(x1 == s1 && x2 == s2){
      if(dr < 1000)
        app[dr] = i - l;
      dr ++;
    }

    x1 -= p1 * str[(i - l)];
    while(x1 < 0)
      x1 += MOD1;
    x1 *= BASE;
    x1 += str[i]; 
    x1 %= MOD1;

    x2 -= p2 * str[(i - l)];
    while(x2 < 0)
      x2 += MOD2;
    x2 *= BASE;
    x2 += str[i];
    x2 %= MOD2;

    i ++;
  }
  if(x1 == s1 && x2 == s2){
    if(dr < MAXP)
      app[dr] = i - l;
    dr ++;
  }

  fout = fopen("strmatch.out", "w");
  fprintf(fout, "%d\n", dr);
  if(dr > MAXP)
    dr = MAXP;
  for(i = 0; i < dr; i ++)
    fprintf(fout, "%d ", app[i]);
  fprintf(fout, "\n");
  fclose(fout);

  return 0;
}