Cod sursa(job #2786999)

Utilizator alexioana_2006Apostolache Alexia alexioana_2006 Data 22 octombrie 2021 11:10:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MOD1=666013;
const int MOD2=10003;
char s[2000001],s2[2000001];
long long h1,h2,v1,v2,poz,nr,n,m,p,r,pozin[20000001],i;
int main()
{ fin>>s>>s2;
  n=strlen(s2); m=strlen(s); p=r=1; nr=0;
h1=h2=s[0]-'0'+1;
  for(i=1;i<m;i++)
  {
      h1=(h1*109%MOD1)+(s[i]-'0'+1)%MOD1;
      h2=(h2*109%MOD2)+(s[i]-'0'+1)%MOD2;
      p=(p*109)%MOD1;
      r=(r*109)%MOD2;
  }

  for(i=0;i<m;i++)
  {
     v1=(v1*109%MOD1)+(s2[i]-'0'+1)%MOD1;
     v2=(v2*109%MOD2)+(s2[i]-'0'+1)%MOD2;
  }

  if(v1==h1 && v2==h2) {nr++; pozin[nr]=0;}

  for(i=m;i<n;i++)
  {
      v1=(1LL*(v1-(1LL*p*(s2[i-m]-'0'+1))%MOD1+MOD1)*109+(s2[i]-'0'+1))%MOD1;
      v2=(1LL*(v2-(1LL*r*(s2[i-m]-'0'+1))%MOD2+MOD2)*109+(s2[i]-'0'+1))%MOD2;
      if(v1==h1 && v2==h2) {nr++; pozin[nr]=i-m+1;}
  }

  fout<<nr<<'\n';
  if(nr<=1000)
   {for(i=1;i<=nr;i++)
        fout<<pozin[i]<<" "; }
  else
    {for(i=1;i<=1000;i++)
        fout<<pozin[i]<<" "; }
    return 0;
}