Cod sursa(job #2362234)

Utilizator serban24Popovici Serban-Florin serban24 Data 3 martie 2019 00:42:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <bits/stdc++.h>
#define MOD1 1000000009
#define MOD2 1000000007
#define baza 63

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string a;
string b;
int nr=0;
vector <int> answer;
int convert[128];

void cautare(){
    long long hash1=0, hash2=0, hash3=0, hash4=0, i, j, n, m, pmax1=1, pmax2=1;

    n=a.size();
    m=b.size();

    for(i=0;i<n;i++){
        hash1*=baza;
        hash1+=convert[a[i]];
        hash1=hash1%MOD1;

        hash2*=baza;
        hash2+=convert[a[i]];
        hash2=hash2%MOD2;

        if(i<n-1){
            pmax1*=baza;
            pmax1=pmax1%MOD1;

            pmax2*=baza;
            pmax2=pmax2%MOD2;
        }
    }

    for(i=0;i<n;i++){
        hash3*=baza;
        hash3+=convert[b[i]];
        hash3=hash3%MOD1;

        hash4*=baza;
        hash4+=convert[b[i]];
        hash4=hash4%MOD2;
    }

    if(hash1==hash3 && hash2==hash4){
        nr++;
        answer.push_back(0);
    }

    for(i=n;i<m;i++){
        hash3-=((convert[b[i-n]])*pmax1)%MOD1-MOD1;
        hash3=hash3%MOD1;
        hash3*=baza;
        hash3+=convert[b[i]];
        hash3=hash3%MOD1;

        hash4-=((convert[b[i-n]])*pmax2)%MOD2-MOD2;
        hash4=hash4%MOD2;
        hash4*=baza;
        hash4+=convert[b[i]];
        hash4=hash4%MOD2;

        if(hash1==hash3 && hash2==hash4){
            nr++;
            answer.push_back(i-n+1);
        }
    }

    fout<<nr<<"\n";

    int val=1;

    for(i=0;i<answer.size() && val<=1000;i++){
        val++;
        fout<<answer[i]<<" ";
    }
}

int main(){
    int i;

    fin>>a>>b;

    for(i='A';i<='Z';i++)
        convert[i]=i-'A'+1;

    for(i='0';i<='9';i++)
        convert[i]=i-'0'+27;

    for(i='a';i<='z';i++)
        convert[i]=i-'a'+37;

    cautare();

    return 0;
}