Cod sursa(job #2729240)

Utilizator YouDontNeedMyNameJurcut Paul YouDontNeedMyName Data 24 martie 2021 14:58:46
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;


string a,b;
// use unsigned for easy modulo
// hash[0] = (a[0]*p^n + a[1]*p^(n-1) + ... + a[n-1]*p + a[n])%mod
// hash[i] = hash[i-1]*p + a[n+i] - p^(n+1)*a[i-1];

void read(){
    ifstream in("strmatch.in");
    in >> a;
    in >> b;
    in.close();
}

void solve(){
    ofstream out("strmatch.out");
    const int p=31;
    const int mod=1e9 + 9;
    long long hash_a=0, hash_b=0, p_n=1;
    vector<int> sol;
    for(unsigned int i=0; i<a.size(); i++){
        hash_a = (hash_a*p + a[i])%mod;
        hash_b = (hash_b*p + b[i])%mod;
        p_n=p_n*p%mod;
    }
    if(hash_a == hash_b) sol.push_back(0);
    for(unsigned int i=a.size(); i<b.size(); i++){
        hash_b = (hash_b*p - p_n*b[i-a.size()] + b[i])%mod;
        if(hash_b == hash_a) sol.push_back(i-a.size()+1);
    }
    out << sol.size() << '\n';
    for(auto elem:sol){
        out << elem << ' ';
    }
    out.close();
}

int main(){
    read();
    solve();
}