Cod sursa(job #2419073)

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

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

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

int main(){
    fin>>a>>b;
    rezolvare();
    afisare();
    return 0;
}
void rezolvare(){
    int 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;
        if(a[i]>='A'&&a[i]<='Z')
            hashA+=a[i]-'A';
        else hashA+=a[i]-'a'+27;
        if(hashA>MOD)hashA%=MOD;
    }
    for(i=0;i<sza;++i){
        hashB=hashB*BAZA;

        if(b[i]>='A'&&b[i]<='Z')
            hashB+=b[i]-'A';
        else hashB+=b[i]-'a'+27;

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

    if(hashA==hashB) Ans[n++]=0;
    for(i=sza;i<szb;++i){
        if(b[i]>='A'&&b[i]<='Z')
            y=b[i]-'A';
        else y=b[i]-'a'+27;

        if(b[i-sza]>='A'&&b[i-sza]<='Z')
            x=b[i-sza]-'A';
        else x=b[i-sza]-'a'+27;

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

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

        if(hashA==hashB) Ans[n++]=i-sza+1;
    }
}
int Exp(long long  x,int 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(){
    int i;
    fout<<n<<'\n';
    for(i=0;i<n;++i)
        fout<<Ans[i]<<' ';
    fout<<'\n';
}