Cod sursa(job #2793359)

Utilizator teochess2017Togan Teodor-Bogdan teochess2017 Data 3 noiembrie 2021 15:26:42
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.84 kb
#include <iostream>
#include <stdio.h>

using namespace std;

#define BAZA 62
#define MOD1 1000007
#define MOD2 666013
#define MAXLENGHT 2000000
#define MAXOUT 1000

char pat[MAXLENGHT], v[MAXLENGHT];
int out[MAXOUT];
int hpat[2], hss[2], put[2];

int verif(int n, int st, int dr){
  int i, f = 1;
  i = 0;
  while(( f ) && (i < n)){
    if(pat[i] != v[i + st]){
      f = 0;
    }
    i++;
  }
  return f;
}

int main()
{
    FILE *fin, *fout;
    char ch;
    int i, n, ind, cod, codaux, additional;
    ch = 0;
    i = 0;
    hpat[0] = 0;
    fin = fopen("strmatch.in", "r");
    while((ch = fgetc(fin)) != '\n'){
      pat[i] = ch;
      if(('A' <= ch) && (ch <= 'Z')){
        cod = ch - 'A';
      }else if(('a' <= ch) && (ch <= 'z')){
        cod = ch - 'a' + 26;
      }else{
        cod = ch - '0' + 52;
      }
      hpat[0] = (BAZA * hpat[0] + cod) % MOD1;
      hpat[1] = (BAZA * hpat[1] + cod) % MOD2;
      i++;
    }
    n = i;
    i = 0;
    ch = 0;
    ind = 0;
    put[0] = put[1] = 1;
    additional = 0;
    while(((ch = fgetc(fin)) != '\n') && (ch != EOF)){
      v[i] = ch;
      if(('A' <= ch) && (ch <= 'Z')){
        cod = ch - 'A';
      }else if(('a' <= ch) && (ch <= 'z')){
        cod = ch - 'a' + 26;
      }else{
        cod = ch - '0' + 52;
      }
      if(i < n){
        hss[0] = (BAZA * hss[0] + cod) % MOD1;
        hss[1] = (BAZA * hss[1] + cod) % MOD2;
        if(i == (n - 1)){
          if((hss[0] == hpat[0]) && (hss[1] == hpat[1])){
            if(verif(n, 0, i + 1)){
              out[ind] = i - n + 1;
              ind++;
            }
          }
        }else{
          put[0] = (put[0] * BAZA) % MOD1;
          put[1] = (put[1] * BAZA) % MOD2;
        }
      }else{
        if(('A' <= v[i - n]) && (v[i - n] <= 'Z')){
          codaux = v[i - n] - 'A';
        }else if(('a' <= v[i - n]) && (v[i - n] <= 'z')){
          codaux = v[i - n] - 'a' + 26;
        }else{
          codaux = v[i - n] - '0' + 52;
        }
        hss[0] = hss[0] - (codaux * put[0]) % MOD1;
        hss[1] = hss[1] - (codaux * put[1]) % MOD2;
        if(hss[0] < 0){
          hss[0] += MOD1;
        }
        if(hss[1] < 0){
          hss[1] += MOD2;
        }
        hss[0] = (hss[0] * BAZA + cod) % MOD1;
        hss[1] = (hss[1] * BAZA + cod) % MOD2;
        if((hss[0] == hpat[0]) && (hss[1] == hpat[1])){
          if(verif(n, i - n + 1, i + 1)){
            if(ind < MAXOUT){
              out[ind] = i - n + 1;
              ind++;
            }else{
              additional++;
            }
          }
        }
      }
      i++;
    }
    fclose(fin);
    fout = fopen("strmatch.out", "w");
    fprintf(fout, "%d\n", ind + additional);
    for(i = 0; i < ind; i++){
      fprintf(fout, "%d ", out[i]);
    }
    fclose(fout);
    return 0;
}