Pagini recente » Cod sursa (job #1378634) | Cod sursa (job #3246646) | Cod sursa (job #1575474) | Cod sursa (job #892674) | Cod sursa (job #2154456)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int MAXN = 2000005;
const int MOD1 = 666013;
const int MOD2 = 1e9 + 7;
const int Q = 3;
int n, m;
long long ha, ha2, hb, hb2, P1, P2;
char A[MAXN], B[MAXN];
vector<int> sol;
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;
for (int i = 1; i < m; ++i) {
P1 = (P1 * Q) % MOD1;
P2 = (P2 * Q) % MOD2;
}
// calculeaza hash-ul lui A si B[0..m-1]
for (int i = 0; i < m; ++i) {
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.push_back(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.push_back(i);
if (sol.size() == 1000) break;
}
}
out << sol.size() << "\n";
for (int i : sol) out << i << " ";
return 0;
}