Cod sursa(job #2632948)

Utilizator Savu_Stefan_CatalinSavu Stefan Catalin Savu_Stefan_Catalin Data 5 iulie 2020 18:34:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#define MOD1 (85636124)
#define MOD2 (93579235)
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
long long pro1,pro2,val1,val2,val3,val4,n,n2,i,nrr,nrr2;
char c,a[2000005];
int main()
{
    pro1=pro2=1;
while (true)
{
    in.get(c);
    if (c=='\n') break;
    val1=(67*val1+c)%MOD1;
    val2=(67*val2+c)%MOD2;
 if (n!=0){
    pro1=67*pro1%MOD1;
    pro2=67*pro2%MOD2;}
    n++;
}
while (true)
{
    in.get(a[i++]);
    if (a[i-1]=='\n') break;
    if (i<=n) {val3=(67*val3+a[i-1])%MOD1;
              val4=(67*val4+a[i-1])%MOD2;
    }
    else {if (val1==val3&&val2==val4) nrr++;
    val3=(67*(val3-pro1*a[i-n-1])%MOD1+MOD1+a[i-1])%MOD1;
    val4=(67*(val4-pro2*a[i-n-1])%MOD2+MOD2+a[i-1])%MOD2;}
}
if (val1==val3&&val2==val4) nrr++;
out<<nrr<<'\n';
n2=i;
val3=val4=0;
for (i=1;i<n2;++i)
{
    if (i<=n) {val3=(67*val3+a[i-1])%MOD1;
              val4=(67*val4+a[i-1])%MOD2;
    }
    else {if (val1==val3&&val2==val4) {nrr2++;
        if (nrr2>1000) return 0;
        out<<i-n-1<<" ";
    }
    val3=(67*(val3-pro1*a[i-n-1])%MOD1+MOD1+a[i-1])%MOD1;
    val4=(67*(val4-pro2*a[i-n-1])%MOD2+MOD2+a[i-1])%MOD2;}
}
     if (val1==val3&&val2==val4) {nrr2++;
        if (nrr2>1000) return 0;
        out<<i-n-1<<" ";
    }


    return 0;
}