Pagini recente » Borderou de evaluare (job #355816) | Borderou de evaluare (job #2247368) | Cod sursa (job #3157081) | Borderou de evaluare (job #1713634) | Cod sursa (job #2385017)
#include <fstream>
#include <vector>
#include <string>
#define MOD1 100003
#define MOD2 100021
#define PRIM1 17
#define PRIM2 127
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A, B;
vector <int> rez;
unsigned long long hashA1, hashA2, P1 = 1, P2 = 1, hashB1, hashB2;
int szA, szB, nr = 0;
int main()
{
f >> A >> B;
szA = A.size();
szB = B.size();
if (szA > szB){
g << "0";
return 0;
}
//hash sablon
for(int i=0; i<szA; ++i){
hashA1 = ((hashA1 * PRIM1) + A[i]);
hashA2 = ((hashA2 * PRIM2) + A[i]);
//P1 = P ^ (m-1)
if(i!=0){
P1 = (P1 * PRIM1);
P2 = (P2 * PRIM2);
}
}
//hash primele szA char-uri din B
for(int i=0; i<szA; ++i){
hashB1 = ((hashB1 * PRIM1) + B[i]);
hashB2 = ((hashB2 * PRIM2) + B[i]);
}
if(hashA1 == hashB1 && hashA2 == hashB2){
rez.push_back(0);
++nr;
}
//Restul de substringuri de lungime szA
for(int i=szA; i<=szB; ++i){
hashB1 = ((PRIM1 * (hashB1 - ((B[i - szA] * P1)) )) + B[i]);
hashB2 = ((PRIM2 * (hashB2 - ((B[i - szA] * P2)) )) + B[i]);
if(hashB1 == hashA1 && hashB2 == hashA2){
rez.push_back(i - szA + 1);
++nr;
}
}
g << nr << '\n';
for(int i=0; i<rez.size() && i<1000; ++i)
g << rez[i] << ' ';
return 0;
}