Cod sursa(job #3277768)

Utilizator PsyDuck1914Feraru Rares-Serban PsyDuck1914 Data 17 februarie 2025 13:21:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("strmatch.in");
ofstream g ("strmatch.out");

int MOD1 = 666013;
int MOD2 = 666013;
int BAZA1 = 512;
int BAZA2 = 798;
const int NMAX = 2e6;

string a, b;

long long pw1[NMAX + 1], pw2[NMAX + 1];

void precalcul(){
    
    pw1[0] = 1;
    pw2[0] = 1;
    
    for(int i=1; i<=NMAX; i ++){
        
        pw1[i] = (pw1[i-1] * BAZA1) % MOD1;
        pw2[i] = (pw2[i-1] * BAZA2) % MOD2;
    }
        
    
}

int hashh(int st, int dr, int mod, int baza, string s, long long pw[]){
    
    long long sum = 0;
    int cnt = 0;
    
    for(int i=dr; i>=st; i--){
        
        sum = (sum + (long long)pw[cnt] * (int)(s[i] - 'a') % mod + mod) % mod;
        
        cnt ++;
        
    }
    
    return sum;
    
}

int hash1a, hash2a;
int hash1b, hash2b;

int rollhash(int hashh, int scot, int add, int mod, int baza, int max_pow, string s, long long pw[]){
    
    return (((hashh - (1LL*pw[max_pow] * (s[scot] - 'a') % mod) + mod) % mod * baza + (s[add] - 'a')) % mod);
    
}

int main()
{
    
    precalcul();
    
    f >> a >> b;
    
    hash1a = hashh(0, a.size()-1, MOD1, BAZA1, a, pw1);
    hash2a = hashh(0, a.size()-1, MOD2, BAZA2, a, pw2);
    
    hash1b = hashh(0, a.size()-1, MOD1, BAZA1, b, pw1);
    hash2b = hashh(0, a.size()-1, MOD2, BAZA2, b, pw2);
    
    int cnt = 0;
    
    vector<int> rez;
    
    if(hash1a == hash1b and hash2a == hash2b)
        rez.push_back(0);
        
    for(int i=a.size(); i<b.size(); i++){
        
        hash1b = rollhash(hash1b, i - a.size(), i, MOD1, BAZA1, a.size() - 1, b, pw1);
        hash2b = rollhash(hash2b, i - a.size(), i, MOD2, BAZA2, a.size() - 1, b, pw2);
        
        if(hash1a == hash1b and hash2a == hash2b)
            rez.push_back(i - a.size() + 1);
        
    }
    
    g << rez.size() << "\n";
    for(int i=0; i<min((int)rez.size(), 1000); i++)
        g << rez[i] << ' ';

    return 0;
}