Pagini recente » Cod sursa (job #1565872) | Cod sursa (job #2984032) | Cod sursa (job #888197) | Cod sursa (job #114843) | Cod sursa (job #2969251)
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define M 1000000007
#define p 31
#define MAX_LEN 2000001
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[MAX_LEN], b[MAX_LEN];
int sol[MAX_LEN];
int n;
void citire() {
fin >> a;
fin.get();
fin >> b;
}
ull get_hash(char* s, int len) {
ull h = 0;
for (int i = 0; i < len; i++) {
h = (h * p + s[i]) % M;
}
return h;
}
ull get_pow(int len) {
ull res = 1;
for (int i = 0; i < len; i++) {
res = (res * p) % M;
}
return res;
}
void rabinkarp() {
int la = strlen(a);
int lb = strlen(b);
if (la > lb) {
fout << 0;
return;
}
ull ha = get_hash(a, la);
ull hb = get_hash(b, la);
ull pow = get_pow(la - 1);
if (ha == hb) {
sol[0] = 1;
n++;
}
for (int i = la; i < lb; i++) {
hb = ((hb - b[i - la] * pow % M) + M) % M;
hb = (hb * p + b[i]) % M;
if (hb == ha) {
sol[i - la + 1] = 1;
n++;
}
}
fout << n << endl;
n = 0;
for (int i = 0; i < lb && n < 1000; i++) {
if (sol[i]) {
fout << i << " ";
n++;
}
}
}
int main() {
citire();
rabinkarp();
return 0;
}