Pagini recente » Cod sursa (job #3156878) | Cod sursa (job #1851673) | Cod sursa (job #2772970) | Cod sursa (job #345576) | Cod sursa (job #2791110)
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
#define NMAX 2000005
char a[NMAX], b[NMAX];
int nrla, nrlb, nrrez, pozrez[1005];
class Hash {
private:
long long n, d, p, put, val, poz;
char *str;
public:
Hash(int nn, int pp, int dd, char *strr) {
n = nn;
p = pp;
d = dd;
put = 1;
val = 0;
poz = 0;
str = strr;
}
void init() {
for (int i = n - 1; i >= 0; --i) {
val = (val + (put * str[i]) % p) % p;
if (i)
put = (put * d) % p;
}
}
void roll() {
val = (((val - (put * str[poz]) % p + p) % p * d) % p + str[poz + n]) % p;
poz++;
}
long long get_val() {
return val;
}
};
void citire() {
scanf("%s", &a);
scanf("%s", &b);
nrla = strlen(a);
nrlb = strlen(b);
}
void cautare() {
Hash ha1 = Hash(nrla, 100007, 71, a);
Hash hb1 = Hash(nrla, 100007, 71, b);
Hash ha2 = Hash(nrla, 100021, 71, a);
Hash hb2 = Hash(nrla, 100021, 71, b);
ha1.init();
hb1.init();
ha2.init();
hb2.init();
for (int i = 0; i < nrlb - nrla + 1; ++i) {
if (ha1.get_val() == hb1.get_val() && ha2.get_val() == hb2.get_val()) {
nrrez++;
if (nrrez <= 1000)
pozrez[nrrez] = i;
}
hb1.roll();
hb2.roll();
}
}
void afisare() {
printf("%d\n", nrrez);
int poz = min(nrrez, 1000);
for (int i = 1; i <= poz; ++i)
printf("%d ", pozrez[i]);
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citire();
if (nrla > nrlb) {
printf("%d", 0);
return 0;
}
cautare();
afisare();
return 0;
}