Pagini recente » Cod sursa (job #55828) | Cod sursa (job #2970185) | Cod sursa (job #2589857) | Cod sursa (job #1661165) | Cod sursa (job #2008280)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
typedef unsigned int UI;
const int MAXN = 2000005;
const UI MOD1 = 100007;
const UI MOD2 = 100009;
const UI B = 73;
char a[MAXN], b[MAXN];
UI ha, ha2, hb, hb2, p1, p2;
int n, m;
int sol[1001];
inline void preprocess() {
p1 = 1;
p2 = 1;
for (int i = 0; i <= m; ++i) {
if (i != 0) {
p1 = (p1 * B) % MOD1;
p2 = (p2 * B) % MOD2;
}
ha = (ha * B + a[i]) % MOD1;
ha2 = (ha2 * B + a[i]) % MOD2;
hb = (hb * B + b[i]) % MOD1;
hb2 = (hb2 * B + b[i]) % MOD2;
}
}
int main()
{
in >> a;
in >> b;
n = strlen(b) - 1;
m = strlen(a) - 1;
preprocess();
for (int i = 0; i <= n - m; ++i) {
if (i != 0) {
hb = ((hb - (b[i - 1] * p1) % MOD1 + MOD1) * B + b[i + m]) % MOD1;
hb2 = ((hb2 - (b[i - 1] * p2) % MOD2 + MOD2) * B + b[i + m]) % MOD2;
}
if (ha == hb && ha2 == hb2) {
sol[0]++;
if (sol[0] <= 1000) sol[sol[0]] = i;
}
}
out << sol[0] << "\n";
int stop = min(sol[0], 1000);
for (int i = 1; i <= stop; ++i) {
out << sol[i] << " ";
}
return 0;
}