Pagini recente » Cod sursa (job #1747158) | Cod sursa (job #405992) | Cod sursa (job #1036817) | Cod sursa (job #2372253) | Cod sursa (job #2378747)
#include <fstream>
#include <vector>
#include <string>
#define MOD1 100003
#define MOD2 100021
#define PRIM1 33
#define PRIM2 73
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) % MOD1 + A[i]) % MOD1;
hashA2 = ((hashA2 * PRIM2) % MOD2 + A[i]) % MOD2;
//P1 = P ^ (m-1)
if(i!=0){
P1 = (P1 * PRIM1) % MOD1;
P2 = (P2 * PRIM2) % MOD2;
}
}
//hash primele szA char-uri din B
for(int i=0; i<szA; ++i){
hashB1 = ((hashB1 * PRIM1) % MOD1 + B[i]) % MOD1;
hashB2 = ((hashB2 * PRIM2) % MOD2 + B[i]) % MOD2;
}
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) % MOD1) )) % MOD1 + B[i]) % MOD1;
hashB2 = ((PRIM2 * (hashB2 - ((B[i - szA] * P2) % MOD2) )) % MOD2 + B[i]) % MOD2;
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;
}