Cod sursa(job #1982239)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 17 mai 2017 22:50:15
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MODA=100007;
const int MODB=100003;
const int BASE=74;
char sircmp[2000000];
char sirm[2000000];
int rez [1001];
int transf(int x){
  return x-'0';
}
int main()
{
    FILE*fin,*fout;
    int i,n,j,m,codma,codmb,codla,codlb;
    fin=fopen("strmatch.in","r");
    fgets(sircmp,2000001,fin);
    fgets(sirm,2000001,fin);
    m=strlen(sircmp)-1;
    n=strlen(sirm)-1;
    codma=0;
    codmb=0;
    int mBASEa=1,mBASEb=1;
    for(int p=0;p<m-1;p++){
      mBASEa=(mBASEa*BASE)%MODA;
      mBASEb=(mBASEb*BASE)%MODB;
    }
    for(i=0;i<m;i++){
      codma=(codma*BASE + transf(sircmp[i]))%MODA;
      codmb=(codmb*BASE + transf(sircmp[i]))%MODB;
    }
    j=0;
    codla=0;
    codlb=0;
    fout=fopen("strmatch.out","w");
    for(i=0;i<m && i<n;i++){
      codla=(codla*BASE + transf(sirm[i]))%MODA;
      codlb=(codlb*BASE + transf(sirm[i]))%MODB;
    }
    if(codla==codma && codlb==codmb)
      rez[j++]=0;
    for(i=m;i<n;i++){
      codla=(((codla+MODA-transf(sirm[i-m])*mBASEa+MODA)%MODA)*BASE+ transf(sirm[i]))%MODA;
      codlb=(((codlb+MODB-transf(sirm[i-m])*mBASEb+MODB)%MODB)*BASE+ transf(sirm[i]))%MODB;
      if(codla==codma && codlb==codmb){
        if(j<=1000)
          rez[j++]=i-m+1;
        else
          j++;
      }
    }
    fprintf(fout,"%lld\n",j);
    if(j>1000)
      j=1000;
    for(i=0;i<j;i++)
      fprintf(fout,"%lld ",rez[i]);
    return 0;
}