Pagini recente » Cod sursa (job #1645475) | Cod sursa (job #1364262) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #2222893)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define NMAX 2000001
#define PRIM1 48487
#define PRIM2 59197
using namespace std;
int hash1, hash2;
char a[NMAX], b[NMAX];
class vec
{
int v[NMAX];
int siz;
public:
int size()
{
return siz;
}
vec():siz(0){}
void push_back(int x)
{
v[siz++] = x;
}
void afisare()
{
int minim = (siz < 1000) ? siz : 1000;
for(int i = 0; i < minim; ++i)
printf("%d ", v[i]);
}
} ans;
const int pondere = 123;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", &a);
scanf("%s", &b);
int sizeA = strlen(a);
int pondere1 = 1, pondere2 = 1;
hash1 = a[0];
hash2 = a[0];
for(int i = 1; i < sizeA; ++i)
{
hash1 = (hash1 * pondere + a[i]) % PRIM1;
hash2 = (hash2 * pondere + a[i]) % PRIM2;
pondere1 = (pondere1 * pondere) % PRIM1;
pondere2 = (pondere2 * pondere) % PRIM2;
}
int bHash1 = 0;
int bHash2 = 0;
for(int i = 0; i < sizeA - 1; ++i)
{
bHash1 = (bHash1 * pondere + b[i]) % PRIM1;
bHash2 = (bHash2 * pondere + b[i]) % PRIM2;
}
for(int i = sizeA - 1; b[i] != NULL; ++i)
{
bHash1 = (bHash1 * pondere + b[i]) % PRIM1;
bHash2 = (bHash2 * pondere + b[i]) % PRIM2;
int beginPos = i - sizeA + 1;
if(hash1 == bHash1 && hash2 == bHash2)
{
ans.push_back(beginPos);
}
bHash1 = (bHash1 - ((b[beginPos] * pondere1) % PRIM1) + PRIM1) % PRIM1;
bHash2 = (bHash2 - ((b[beginPos] * pondere2) % PRIM2) + PRIM2) % PRIM2;
}
printf("%d\n", ans.size());
ans.afisare();
return 0;
}