Pagini recente » Cod sursa (job #1001595) | Cod sursa (job #1772347) | Cod sursa (job #2543085) | Cod sursa (job #462841) | Cod sursa (job #2154474)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int MAXN = 2000005;
const int MOD1 = 1000003;
const int MOD2 = 1000033;
const int Q = 73;
int n, m;
int 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) % MOD1;
P2 = (P2 * Q) % MOD2;
}
ha = (ha * Q + A[i]) % MOD1;
ha2 = (ha2 * Q + A[i]) % MOD2;
hb = (hb * Q + B[i]) % MOD1;
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 + MOD1) * Q + B[i + m - 1]) % MOD1;
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;
}