Cod sursa(job #1000904)

Utilizator alexx.cosmaCosma Cristian Alexandru alexx.cosma Data 23 septembrie 2013 22:27:18
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int aparPos[2000000];

void rabinKarp(string a, string b);

int main()
{
    string A,B;
    fin >> A;
    fin >> B;

    rabinKarp(A,B);
    return 0;
}

int hashMe(string a){
    int sum=0;
    int len = a.size();
    for(int i=0; i<len;i ++){
        sum += a[i];
    }
    return sum;
}

void rabinKarp(string a, string b){
    int sizeA = a.size();
    int sizeB = b.size();

    int nrOfAparitions=0;

    int hashA = hashMe(a);
    int hashB = hashMe(b.substr(0,sizeA));

    // we can recompute hashB by simply substracting last index and adding next

    for (int i=0; i<sizeB - sizeA + 1; i++){
        if(hashA == hashB){
            //if(a == b.substr(i,i+sizeA -1)){
                aparPos[nrOfAparitions]=i;
                nrOfAparitions++;
          //  }
        }
        hashB = hashB - b[i] + b[i+sizeA];
    }

    fout << nrOfAparitions << '\n';

    for(int i=0;i<nrOfAparitions;i++){
        fout << aparPos[i] << ' ';
    }

}