Cod sursa(job #2419085)

Utilizator AlexBolfaAlex Bolfa AlexBolfa Data 7 mai 2019 17:27:21
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>
#define MAX 1005
#define BAZA 121
#define MOD (long long)(1e9+7)
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

long long Ans[MAX],n,nr,sza,szb,hashA,hashB,x,y;
string a,b;

void afisare();
void rezolvare();
long long Exp(long long,long long);

int main(){
    fin>>a>>b;
    rezolvare();
    afisare();
    return 0;
}
void rezolvare(){
    long long i,putere;
    sza=a.size();
    szb=b.size();
    if(szb<sza)return;

    putere=Exp(BAZA,sza-1);
    for(i=0;i<sza;++i){
        hashA=hashA*BAZA;

        hashA+=a[i]-'0';

        if(hashA>MOD)hashA%=MOD;
    }
    for(i=0;i<sza;++i){
        hashB=hashB*BAZA;

        hashB+=b[i]-'0';

        if(hashB>MOD)hashB%=MOD;
    }

    if(hashA==hashB) Ans[n++]=0;
    for(i=sza;i<szb;++i){
        x=b[i-sza]-'0';
        y=b[i]-'0';

        hashB=(hashB-x*putere+MOD)%MOD*BAZA+y;

        if(hashA>MOD)hashA%=MOD;
        if(hashB>MOD)hashB%=MOD;

        if(hashA==hashB){
            if(nr<1000)Ans[nr++]=i-sza+1;
            ++n;
        }

    }
}
long long Exp(long long  x,long long n){
    long long p=1;
    while(n){
        if(n%2){
            p*=x;
            --n;
            if(p>MOD)p%=MOD;
        }
        x*=x;
        n/=2;
        if(x>MOD)x%=MOD;
    }
    return (p%MOD);
}
void afisare(){
    long long i;
    fout<<n<<'\n';
    for(i=0;i<nr;++i)
        fout<<Ans[i]<<' ';
    fout<<'\n';
}