Cod sursa(job #2539397)

Utilizator stef2003Bud Stefan stef2003 Data 5 februarie 2020 20:33:45
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

char a[2000001], b[2000001];
int v[2000001];
int main() {
  FILE *fin, *fout;
  int n, m, x1, x2, y1, y2, nr, i, mod1=666013, mod2=1000003, p1, p2;
  fin=fopen("strmatch.in","r");
  fout=fopen("strmatch.out","w");
  fscanf(fin, "%s\n%s",&a,&b);
  n=strlen(a);
  m=strlen(b);
  if(n>m) {
    fprintf(fout, "0");
    return 0;
  }
  x1=x2=y1=y2=0;
  nr=1;
  p1=p2=1;
  for(i=0;i<n;i++) {
    x1=(x1*27+a[i]-'A'+1)%mod1;
    x2=(x2*27+a[i]-'A'+1)%mod2;
    y1=(y1*27+b[i]-'A'+1)%mod1;
    y2=(y2*27+b[i]-'A'+1)%mod2;
    if(i!=0) {
      p1=(p1*27)%mod1;
      p2=(p2*27)%mod2;
    }
  }
  if(x1==y1 && x2==y2)
    v[nr++]=i-n+1;
  for(i=n;i<m;i++) {
    y1=((y1%p1)*27+b[i]-'A'+1)%mod1;
    y2=((y2%p2)*27+b[i]-'A'+1)%mod2;
    if(x1==y1 && x2==y2)
      v[nr++]=i-n+1;
  }
  fprintf(fout, "%d\n",nr-1);
  for(i=1;i<nr && i<=1000;i++)
    fprintf(fout, "%d ",v[i]);
  fclose( fin );
  fclose( fout );
  return 0;
}