Cod sursa(job #2974869)

Utilizator divadddDavid Curca divaddd Data 4 februarie 2023 19:24:51
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <bits/stdc++.h>
#define SIGMA 73
#define MOD   100007
#define MOD2  100021
using namespace std;
string a,b;
int hasha1,hasha2,hashb1,hashb2,ans;
vector<int> sol;

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

int getpos(char ch){
    if('a' <= ch && ch <= 'z'){
        return (ch-'a');
    }else if('A' <= ch && ch <= 'Z'){
        return 26+(ch-'A');
    }else{
        return 52+(ch-'0');
    }
}

int main()
{
    fin >> a >> b;
    if(a.size() > b.size()){
        fout << "0";
        return 0;
    }
    int pwr = 1;
    for(int i = a.size()-1; i >= 0; i--){
        hasha1 += (getpos(a[i])*pwr)%MOD;
        hasha2 += (getpos(a[i])*pwr)%MOD2;

        hashb1 += (getpos(b[i])*pwr)%MOD;
        hashb2 += (getpos(b[i])*pwr)%MOD2;

        hasha1 %= MOD; hasha2 %= MOD2;
        hashb1 %= MOD; hashb2 %= MOD2;
        if(i != 0){
            pwr *= SIGMA;
            pwr %= MOD;
        }
    }
    if(hasha1 == hashb1 && hasha2 == hashb2){
        ans++;
    }
    for(int i = 1; i < b.size()-a.size()+1; i++){
        hashb1 -= (getpos(b[i-1])*pwr)%MOD;
        hashb2 -= (getpos(b[i-1])*pwr)%MOD2;
        if(hashb1 < 0){
            hashb1 += MOD;
        }
        if(hashb2 < 0){
            hashb2 += MOD2;
        }
        hashb1 *= SIGMA; hashb1 %= MOD;
        hashb2 *= SIGMA; hashb2 %= MOD2;
        hashb1 += getpos(b[i+a.size()-1]); hashb1 %= MOD;
        hashb2 += getpos(b[i+a.size()-1]); hashb2 %= MOD2;
        if(hasha1 == hashb1 && hasha2 == hashb2){
            ans++;
            if(sol.size() < 1000){
                sol.push_back(i);
            }
        }
    }
    fout << ans << "\n";
    for(int it: sol){
        fout << it << " ";
    }
    return 0;
}