Pagini recente » Cod sursa (job #1612464) | Cod sursa (job #860464) | Cod sursa (job #1496564) | Cod sursa (job #2227375) | Cod sursa (job #2008257)
#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[2000001], hb2[2000001], powC[2000002];
int sol[1001];
inline ULL pow(ULL a, int n) {
if (n == 0) return 1;
if (n % 2 == 0) return pow(a * a, n / 2);
return a * pow(a, n - 1);
}
inline void preprocess() {
powC[0] = 1;
ha += a[0] * powC[0];
ha2 += a[0] * pow(C2, 0);
for (int i = 1; i <= n; ++i) {
powC[i] = powC[i - 1] * C;
if (i < m) {
ha += a[i] * powC[i];
ha2 += a[i] * pow(C2, i);
}
}
for (int i = n; i >= 0; --i) {
hb[i] = b[i] + hb[i + 1] * C;
hb2[i] = b[i] + hb2[i + 1] * C2;
}
}
inline void hash_a() {
for (int i = 0; i < m; ++i) {
ha += a[i] * powC[i];
ha2 += a[i] * pow(C2, i);
}
}
int main()
{
int l, r;
ULL h, h2;
in >> a;
in >> b;
n = strlen(b) - 1;
m = strlen(a);
preprocess();
int stop = n - m + 1;
for (int i = 0; i <= stop; ++i) {
l = i;
r = i + m - 1;
h = hb[l] - hb[r + 1] * powC[r - l + 1];
h2 = hb2[l] - hb2[r + 1] * pow(C2, r - l + 1);
if (h == ha && h2 == ha2) {
sol[0]++;
if (sol[0] <= 1000) sol[sol[0]] = i;
}
}
out << sol[0] << "\n";
stop = min(sol[0], 1000);
for (int i = 1; i <= stop; ++i) {
out << sol[i] << " ";
}
return 0;
}