Pagini recente » Cod sursa (job #2790203) | Cod sursa (job #2950627) | Cod sursa (job #573939) | Cod sursa (job #1027491) | Cod sursa (job #2787384)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#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() {
f >> a >> 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() {
g << nrrez << '\n';
int poz = min(nrrez, 1000);
for (int i = 1; i <= poz; ++i)
g << pozrez[i] << ' ';
}
int main() {
citire();
if (nrla > nrlb) {
g << 0;
return 0;
}
cautare();
afisare();
return 0;
}