Cod sursa(job #1679963)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 8 aprilie 2016 13:47:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <string.h>
#define NMAX 1000
using namespace std;
static const int MOD = 131;
static const int base = 128;
string Pattern, String;
vector<int> Sol;
int stringSize, patternSize;

void Read();
void Rabin_Karp();
void Write();

int main()
{
    Read();
    Rabin_Karp();
    Write();
    return 0;
}
void Write()
{
    cout << Sol.size() << '\n';     //Number of matches
    for(int i = 0; i < Sol.size(); ++i)
        cout << Sol[i] << ' ';
}
void Rabin_Karp()
{
    unsigned long base_M_minus_1, hashP, hashS;
    base_M_minus_1 = 1;
    if(patternSize > stringSize)
        return;
    hashP = hashS = 0;
    for(int i = 0; i < patternSize; ++i) {
        hashP = (hashP * base + (Pattern[i] - 48) ) % MOD;
        hashS = (hashS * base + (String[i] - 48) ) % MOD;
        if( i > 0 )
            base_M_minus_1 = (base_M_minus_1 * base ) % MOD;
    }
    for(int i = patternSize; i <= stringSize; ++i) {
        if(hashS == hashP)
            if(String.compare(i - patternSize, patternSize, Pattern) == 0)            //Match
                Sol.push_back(i - patternSize);
        hashS = ( hashS + ( base * MOD ) - ( ( String[i - patternSize] - 48 ) * base_M_minus_1 ) ) % MOD;
        hashS = ( hashS * base + String[i] - 48 ) % MOD;
    }
}
void Read()
{
    freopen("strmatch.in", "rt", stdin);
    freopen("strmatch.out", "wt", stdout);
    cin >> Pattern >> String;
    patternSize = Pattern.size();
    stringSize = String.size();
}