Cod sursa(job #1982344)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 18 mai 2017 14:25:05
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MODA=100043;
const int MODB=100003;
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;
    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 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 + 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])*m62a)%MODA)*62+ transf(sirm[i]))%MODA;
      codlb=(((codlb+MODB-transf(sirm[i-m])*m62b)%MODB)*62+ 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;
}