Cod sursa(job #3036437)

Utilizator begusMihnea begus Data 24 martie 2023 12:34:51
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MOD=1e9+9;

long long hasher1(string s){
    long long hs = 5381;
    for(int i=0; i<s.length(); i++){
        hs = (hs<<5)+hs+s[i];
        hs%=MOD;
    }
    return hs;
}

long long hasher2(string s){
    long long hs = 5381;
    for(int i=0; i<s.length(); i++){
        hs = (hs<<5)+5*hs+s[i];
        hs%=MOD;
    }
    return hs;
}

int main(){
    string s, t;
    fin >> s >> t;
    long long termH1 = hasher1(s), termH2=hasher2(s);
    int ans=0;
    queue<int> pos;
    for(int i=0; i<t.length()-s.length(); i++){
        if(termH1==hasher1(t.substr(i, s.length())) && termH2==hasher2(t.substr(i, s.length()))){
            ans++;
            pos.push(i);
        }
    }
    fout << ans << '\n';
    while(!pos.empty()){
        fout << pos.front() << ' '; pos.pop();
    }
}