Pagini recente » Istoria paginii runda/ojiiiii | Istoria paginii runda/porc3 | Cod sursa (job #405942) | Cod sursa (job #336959) | Cod sursa (job #1000917)
#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 ; i++){
if(hashA == hashB){
if(a.compare(b.substr(i,i+sizeA))){
aparPos[nrOfAparitions]=i;
nrOfAparitions++;
}
}
hashB = hashB - b[i] + b[i+sizeA];
}
fout << nrOfAparitions << '\n';
for(int i=0;i<nrOfAparitions;i++){
fout << aparPos[i] << ' ';
}
}