Cod sursa(job #1982365)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 18 mai 2017 15:23:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MODA=666013;
const int MODB=1000003;
const int BASE=62;
char sircmp[2000005];
char sirm[2000005];
int rez [1005];
int transf(char x){
  if(x>='a' && x<='z')
    return 10 + x - 'a';
  if(x>='A' && x<='Z')
    return 11 + 'z' - 'a' + x- 'A';
  return x-'0';
}

int main()
{
    FILE*fin,*fout;
    int  i,n,j,m,codma,codmb,codla,codlb;
    int uelema,uelemb;
    fin=fopen("strmatch.in","r");
    fgets(sircmp,2000006,fin);
    fgets(sirm,2000006,fin);
    m=strlen(sircmp)-1;
    n=strlen(sirm)-1;
    codma=0;
    codmb=0;
    int m62a=1,m62b=1;
    for(int p=0;p<m-1;p++){
      m62a=(m62a*62)%MODA;
      m62b=(m62b*62)%MODB;
    }
    for(i=0;i<m;i++){
      codma=(codma*BASE%MODA + transf(sircmp[i]))%MODA;
      codmb=(codmb*BASE%MODB+ 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)%MODA + transf(sirm[i]))%MODA;
      codlb=((codlb*BASE)%MODB + transf(sirm[i]))%MODB;
    }

    if(codla==codma && codlb==codmb)
      rez[j++]=0;
    for(i=m;i<n;i++){
      int lit=transf(sirm[i-m]);
      uelema=(lit*m62a)%MODA;
      uelemb=(lit*m62b)%MODB;
      codla=((((codla+MODA-uelema)%MODA)*62)%MODA+transf(sirm[i]))%MODA;
      codlb=((((codlb+MODB-uelemb)%MODB)*62)%MODB+transf(sirm[i]))%MODB;
      if(codla==codma && codlb==codmb){
        if(j<=1000)
          rez[j++]=i-m+1;
        else
          j++;
      }
    }
    fprintf(fout,"%d\n",j);
    if(j>1000)
      j=1000;
    for(i=0;i<j;i++)
      fprintf(fout,"%d ",rez[i]);
    return 0;
}