Cod sursa(job #1680525)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 8 aprilie 2016 20:32:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <string.h>
#define NMAX 2000002
using namespace std;
static const int fMOD = 20011;
static const int sMOD = 20001;
static const int base = 256;
char Pattern[NMAX], String[NMAX];
int stringSize, patternSize, nrMatches;
vector<int> Sol;

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

int main()
{
    Read();
    Rabin_Karp();
    Write();
    return 0;
}
void Write()
{
    cout << nrMatches << '\n';     //Number of matches
    for(int i = 0; i < nrMatches && i < 1000; ++i)
        cout << Sol[i] << ' ';
}
void Rabin_Karp()
{
    int fBasePow, fHashP, fHashS, sBasePow, sHashP, sHashS;
    fBasePow = sBasePow = 1;
    if(patternSize > stringSize)    return;
    fHashP = fHashS = sHashP = sHashS = 0;

    for(int i = 0; i < patternSize; ++i) {
        fHashP = (fHashP * base + (Pattern[i] - 48) ) % fMOD;
        fHashS = (fHashS * base + (String[i] - 48) ) % fMOD;
        sHashP = (sHashP * base + (Pattern[i] - 48) ) % sMOD;
        sHashS = (sHashS * base + (String[i] - 48) ) % sMOD;
        if( i > 0 ) {
            fBasePow = (fBasePow * base ) % fMOD;
            sBasePow = (sBasePow * base ) % sMOD;
        }
    }
    for(int i = patternSize; i <= stringSize; ++i) {
        if(fHashS == fHashP && sHashS == sHashP)// && (String.compare(i - patternSize, patternSize, Pattern) == 0)
        {
            nrMatches++;
            if(nrMatches < 1001)
                Sol.push_back(i - patternSize);
        }
        fHashS = ( fHashS + ( base * fMOD ) - ( ( String[i - patternSize] - 48 ) * fBasePow ) ) % fMOD;
        fHashS = ( fHashS * base + String[i] - 48 ) % fMOD;
        sHashS = ( sHashS + ( base * sMOD ) - ( ( String[i - patternSize] - 48 ) * sBasePow ) ) % sMOD;
        sHashS = ( sHashS * base + String[i] - 48 ) % sMOD;
    }
}
void Read()
{
    freopen("strmatch.in", "rt", stdin);
    freopen("strmatch.out", "wt", stdout);
    scanf("%s%s", Pattern, String);
    patternSize = strlen(Pattern);
    stringSize = strlen(String);
}