Pagini recente » Cod sursa (job #217122) | Cod sursa (job #3235517) | Cod sursa (job #2641735) | Cod sursa (job #3234642) | Cod sursa (job #311579)
Cod sursa(job #311579)
#include <fstream>
#include <string>
#include <iterator>
#include <vector>
#include <cmath>
using namespace std;
#define NUME "strmatch"
ifstream fi(NUME".in");
ofstream fo(NUME".out");
#define P 666013
// maybe better to be larger than values ( > 'z')
// FIXME: cat mai departe de o putere a lui 2 ?
#define P1 293//67
#define P2 307//83
#define hash1(crt, x) (crt*P1 + x) % P
#define hash2(crt, x) (crt*P2 + x) % P
#define okay(x) ((x) + P) % P
//int H1[P][4], H2[P][4], nr1[P], nr2[P];
vector<int> occ;
string A, B;
int main()
{
int i, j, k, M;
int ptn1 = 0, ptn2 = 0; // hash pt pattern
int power1 = 1, power2 = 1;
int h1 = 0, h2 = 0, nr = 0;
fi >> B >> A;
M = B.size();
for (i = 0; i < M; ++i) {
ptn1 = hash1(ptn1, B[i]), ptn2 = hash2(ptn2, B[i]);
if (!i) continue;
power1 = (power1 * P1) % P;
power2 = (power2 * P2) % P;
}
for (i = 0; i < A.size(); ++i) {
if (i >= M) {
h1 = okay(h1 - (A[i-M] * power1) % P);
h2 = okay(h2 - (A[i-M] * power2) % P);
}
h1 = hash1(h1, A[i]);
h2 = hash2(h2, A[i]);
if (i < M-1) continue;
if (h1 == ptn1 && h2 == ptn2) {
int lim = (int)sqrt(M);
for (j = i-M+1, k = 0; k < M; j++, k ++)
if (A[j] != B[k]) break;
if (k == M) {
nr ++;
if (occ.size() < 1000)
occ.push_back(i-M+1);
}
}
}
fo << nr << "\n";
copy(occ.begin(), occ.end(), ostream_iterator<int>(fo, " "));
return 0;
}