Cod sursa(job #2586466)

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

using namespace std;

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

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

long long lgput(long long a,long long b){
    
    long long r = 1;
    
    while(b){
        
        if(b & 1)
            r = r * a;
        
        a = (a * a) % MOD;
        b >>= 1;
    }
    
    return r;
}

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

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

int main(){
    
    f >> a >> b;
    
    int n = (int)a.size();
    int m = (int)b.size();
    
    if(n > m){
        g << 0;
        return 0;
    }
    
    for(int i = 0;i < n;++i){
        PUTERE = lgput(PRIME,i);
        hashA += a[i] * PUTERE;
        hashB += b[i] * PUTERE;
    }
    
    if(hashA == hashB && match(0))
        sol.push_back(0);
    
    for(int i = n;i < m;++i){
        
        hashB = hashB - b[i - n];
        hashB /= PRIME;
        hashB += b[i] * PUTERE;
        
        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;
}