Cod sursa(job #3277735)

Utilizator PsyDuck1914Feraru Rares-Serban PsyDuck1914 Data 17 februarie 2025 12:55:32
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2e6;
int MOD1 = 666013;
int MOD2 = 666013;
int BAZA1 = 29;
int BAZA2 = 31;

string a, b;

int hashh(int st, int dr, int mod, int baza, string s){
    
    long long sum = 0;
    int cnt = 0;
    
    for(int i=dr; i>=st; i--){
        
        sum = (sum + (long long)pow(baza, cnt) % mod * (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){
    
    return (((hashh - (long long)pow(baza, max_pow) % mod * (s[scot] - 'a') % mod + mod) % mod * baza % mod + (s[add] - 'a') % mod) % mod);
    
}

int main()
{
    
    f >> a >> b;
    
    hash1a = hashh(0, a.size()-1, MOD1, BAZA1, a);
    hash2a = hashh(0, a.size()-1, MOD2, BAZA2, a);
    
    hash1b = hashh(0, a.size()-1, MOD1, BAZA1, b);
    hash2b = hashh(0, a.size()-1, MOD2, BAZA2, b);
    
    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);
        hash2b = rollhash(hash2b, i - a.size(), i, MOD2, BAZA2, a.size() - 1, b);
        
        if(hash1a == hash1b and hash2a == hash2b)
            rez.push_back(i - a.size() + 1);
        
    }
    
    g << rez.size() << "\n";
    for(int poz : rez)
        g << poz << ' ';

    return 0;
}