Cod sursa(job #2532464)

Utilizator YouDontNeedMyNameJurcut Paul YouDontNeedMyName Data 27 ianuarie 2020 20:55:38
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>
#define nmax 1024
#define hmax 105
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
vector<int> sol;
int nrHash=5;
long long cst[hmax];
long long ncst[hmax];
long long p[hmax];
long long mod[hmax];
long long pw[hmax];
void init(){
    for(int i=0; i<nrHash; i++){
        mod[i] = 100000000 + rand()%100000000;
        pw[i] = 20 + rand()%23;
        p[i] = 1;
    }
}
bool verif(){
    for(int i=0; i<nrHash; i++){
        if(cst[i]!=ncst[i]) return false;
    }
    return true;
}
void afis(){
    out << sol.size() << '\n';
    for(auto x:sol) cout << x << ' ';
}
void read(){
    in >> a >> b;
    for(int i=0; i<a.size(); i++){
        for(int j=0; j<nrHash; j++){
            cst[j]=(cst[j]*pw[j] + a[i])%mod[j];
            p[j]=p[j]*pw[j]%mod[j];
        }
    }
    if(b.size()<a.size()){
        out << "0";
        exit(0);
    }
    for(int i=0; i<a.size(); i++){
        for(int j=0; j<nrHash; j++){
            ncst[j] = (ncst[j]*pw[j]+b[i])%mod[j];
        }
    }
    for(int i=a.size(); i<b.size(); i++){
        if(verif()){
            sol.push_back(i-a.size());
            if(sol.size()==1000){
                afis();
                exit(0);
            }
        }
        for(int j=0; j<nrHash; j++){
            ncst[j] = (mod[j] + ncst[j]*pw[j] - b[i-a.size()]*p[j]%mod[j] + b[i])%mod[j];
        }
    }
    afis();
}
int main(){
    init();
    read();
}