Pagini recente » Cod sursa (job #3184057) | Cod sursa (job #2986346) | Cod sursa (job #526211) | Cod sursa (job #487492) | Cod sursa (job #2159093)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
typedef unsigned long long LL;
const int MAXN = 2000005;
const LL MOD1 = ((LL)1 << 64);
const LL MOD2 = 1000033;
const LL Q = 77;
int n, m;
LL ha, ha2, hb, hb2, P1, P2;
char A[MAXN], B[MAXN];
int sol[1005];
int main()
{
in >> A >> B;
n = strlen(B);
m = strlen(A);
if (m > n) {
out << 0;
return 0;
}
// calculeaza Q^(m-1)
P1 = P2 = 1;
// calculeaza hash-ul lui A si B[0..m-1]
for (int i = 0; i < m; ++i) {
if (i != 0) {
P1 = (P1 * Q);
P2 = (P2 * Q) % MOD2;
}
ha = (ha * Q + A[i]);
ha2 = (ha2 * Q + A[i]) % MOD2;
hb = (hb * Q + B[i]);
hb2 = (hb2 * Q + B[i]) % MOD2;
}
if (ha == hb && ha2 == hb2) sol[++sol[0]] = 0;
for (int i = 1; i <= n - m; ++i) {
hb = ((hb - (B[i-1] * P1) + MOD1) * Q + B[i + m - 1]);
hb2 = ((hb2 - (B[i-1] * P2) % MOD2 + MOD2) * Q + B[i + m - 1]) % MOD2;
if (ha == hb && ha2 == hb2) {
sol[0]++;
if (sol[0] <= 1000) sol[sol[0]] = i;
}
}
out << sol[0] << "\n";
for (int i = 1; i <= min(sol[0], 1000); ++i) out << sol[i] << " ";
return 0;
}