Cod sursa(job #2793265)

Utilizator teochess2017Togan Teodor-Bogdan teochess2017 Data 3 noiembrie 2021 13:17:34
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 kb
#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

#define MOD 1000007
#define MAXLENGHT 2000000
#define MAXOUT 1000

vector <int>h[MOD];

int pat[MAXLENGHT], v[MAXLENGHT], out[MAXOUT];///de pus pe char

int logput(int a, int p){
  if(p == 1){
    return a;
  }else{
    if((p % 2) == 0){
      return logput(((long long)a * a) % MOD, p / 2);
    }else{
      return ((long long)a * logput(((long long)a * a) % MOD, p / 2)) % MOD;
    }
  }
}
int verif(int n, int st, int dr){
  int i, f = 1;
  for(i = 0; i < n; i++){
    if(pat[i] != v[i + st]){
      f = 0;
    }
  }
  return f;
}

int main()
{
    FILE *fin, *fout;
    char ch;
    int i, n, hpat, hss, ind;
    ch = 0;
    i = 0;
    hpat = 0;
    fin = fopen("strmatch.in", "r");
    while((ch = fgetc(fin)) != '\n'){
      pat[i] = ch;
      hpat = (26 * hpat + ch - 'A' + 1) % MOD;
      i++;
    }
    n = i;
    i = 0;
    ch = 0;
    hss = 0;
    ind = 0;
    while((ch = fgetc(fin)) != '\n'){
      v[i] = ch;
      if(ind < MAXOUT){
        if(i < n){
          hss = (26 * hss + ch - 'A' + 1) % MOD;
          if(i == (n - 1)){
            if(hss == hpat){
              if(verif(n, 0, i + 1)){
                out[ind] = i - n + 1;
                ind++;
              }
            }
          }
        }else{
          hss = hss - ((v[i - n] - 'A' + 1) * logput(26, n - 1)) % MOD;
          if(hss < 0){
            hss += MOD;
          }
          hss = (hss * 26 + ch - 'A' + 1) % MOD;
          if(hss == hpat){
            if(verif(n, i - n + 1, i + 1)){
              out[ind] = i - n + 1;
              ind++;
            }
          }
        }
      }
      i++;
    }
    fclose(fin);
    fout = fopen("strmatch.out", "w");
    fprintf(fout, "%d\n", ind);
    for(i = 0; i < ind; i++){
      fprintf(fout, "%d ", out[i]);
    }
    fclose(fout);
    return 0;
}