Cod sursa(job #2586471)

Utilizator marius004scarlat marius marius004 Data 20 martie 2020 22:09:54
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
//Rabin Karp
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

typedef long long ll;

const long long MOD = (1LL << 30);
const long long PRIME = 31;

string a,b;
long long hashA,hashB,PUTERE;
vector<long long>sol;

bool match(long long start){
    
    for(ll i = 0;i < a.size();++i)
        if(a[i] != b[i + start])
            return false;
    
    return true;
}

int main(){
    
    f >> a >> b;
    
    ll n = (int)a.size();
    ll m = (int)b.size();
    
    if(n > m){
        g << 0;
        return 0;
    }
    
    PUTERE = 1;
    for(ll i = 0;i < n;++i){
        hashA = (hashA + a[i] * PUTERE) % MOD;
        hashB = (hashB + b[i] * PUTERE) % MOD;
        PUTERE = (PUTERE * PRIME) % MOD;
    }
    
    if(hashA == hashB && match(0))
        sol.push_back(0);
    
    b += " ";
    for(ll i = n;i <= m;++i){
        
        hashB = (hashB - b[i - n]) % MOD;
        hashB /= PRIME;
        hashB = (hashB + b[i] * PUTERE) % MOD;
        
        while(hashB < 0)
            hashB += MOD;
        
        if(hashA == hashB && match(i - n + 1))
            sol.push_back(i - n + 1);
    }
    
    g << sol.size() << '\n';
    for(int i = 0;i < sol.size() && i < 1000;++i)
        g << sol[i] << ' ';
    
    return 0;
}