Cod sursa(job #2729222)

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

using namespace std;

const unsigned long long 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(){
    ifstream in("strmatch.in");
    in >> a;
    in >> b;
    in.close();
}

void solve(){
    ofstream out("strmatch.out");
    unsigned long long 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);
        }
    }
    out << sol.size() << '\n';
    for(auto elem:sol){
        out << elem << ' ';
    }
    out.close();
}

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