Pagini recente » Cod sursa (job #1625629) | Cod sursa (job #1523924) | Cod sursa (job #2053147) | Cod sursa (job #1206051) | Cod sursa (job #2008266)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
typedef unsigned int ULL;
const int C = 2, C2 = 3;
int n, m;
char a[2000002], b[2000002];
ULL ha, ha2, hb, hb2, powC, powC2;
int sol[1001];
inline void preprocess() {
powC = 1;
powC2 = 1;
for (int i = 0; i <= m; ++i) {
ha += a[i] * powC;
ha2 += a[i] * powC2;
hb += b[i] * powC;
hb2 += b[i] * powC2;
if (i < m) {
powC *= C;
powC2 *= C2;
}
}
}
int main()
{
in >> a;
in >> b;
n = strlen(b) - 1;
m = strlen(a) - 1;
preprocess();
for (int i = 0; i <= n - m; ++i) {
if (ha == hb && ha2 == hb2) {
sol[0]++;
if (sol[0] <= 1000) sol[sol[0]] = i;
}
if (i + m + 1 > n) continue;
hb -= b[i];
hb /= C;
hb += b[i + m + 1] * powC;
hb2 -= b[i];
hb2 /= C2;
hb2 += b[i + m + 1] * powC2;
}
out << sol[0] << "\n";
int stop = min(sol[0], 1000);
for (int i = 1; i <= stop; ++i) {
out << sol[i] << " ";
}
return 0;
}