Cod sursa(job #2729219)

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

using namespace std;

const unsigned int p = 31;
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]
// hash[i] = hash[i-1]*p + a[n+i] - p^(n+1)*a[i-1];

void read(){
    cin >> a;
    cin >> b;
}

void solve(){
    unsigned int hash_a=0, hash_b=0, p_n=1;
    for(unsigned int i=0; i<a.size(); i++){
        hash_a = hash_a*p + a[i];
        hash_b = hash_b*p + b[i];
        p_n*=p;
    }
    vector<int> sol;
    if(hash_a == hash_b){
        sol.push_back(0);
    }
    for(unsigned int i=a.size(); i<b.size() && sol.size()<1000; i++){
        hash_b = hash_b*p + b[i] - b[i-a.size()]*p_n;
        if(hash_a == hash_b){
            sol.push_back(i-a.size()+1);
        }
    }
    cout << sol.size() << '\n';
    for(auto elem:sol){
        cout << elem << ' ';
    }
}

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