Cod sursa(job #2974872)

Utilizator divadddDavid Curca divaddd Data 4 februarie 2023 19:26:22
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>
#define SIGMA 62
#define MOD   333173
using namespace std;
string a,b;
int hasha,hashb,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 hashsecv(string str){
    int pwr = 1;
    int ans = 0;
    for(int i = str.size()-1; i >= 0; i--){
        ans += (getpos(str[i])*pwr)%MOD;
        ans %= MOD;
        pwr *= SIGMA;
        pwr %= MOD;
    }
    return ans;
}

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--){
        hasha += (getpos(a[i])*pwr)%MOD;
        hashb += (getpos(b[i])*pwr)%MOD;
        hasha %= MOD;
        hashb %= MOD;
        if(i != 0){
            pwr *= SIGMA;
            pwr %= MOD;
        }
    }
    if(hasha == hashb){
        ans++;
        sol.push_back(1);
    }
    for(int i = 1; i < b.size()-a.size()+1; i++){
        hashb -= (getpos(b[i-1])*pwr)%MOD;
        if(hashb < 0){
            hashb += MOD;
        }
        hashb *= SIGMA; hashb %= MOD;
        hashb += getpos(b[i+a.size()-1]); hashb %= MOD;
        if(hasha == hashb){
            ans++;
            if(sol.size() < 1000){
                sol.push_back(i);
            }
        }
    }
    fout << ans << "\n";
    for(int it: sol){
        fout << it << " ";
    }
    return 0;
}