Pagini recente » Cod sursa (job #2252056) | Cod sursa (job #2866617) | Cod sursa (job #1358731) | Cod sursa (job #2860698) | Cod sursa (job #2809570)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
struct Hash
{
long long v, mod, n, len, v0;
long long val;
Hash(long long v, long long mod, long long n)
: v(v), mod(mod), n(n), val(0), v0(1)
{}
void init(char *s)
{
len = strlen(s);
for (long long i = n - 1; i >= 0; i--) {
val = (val + (1ll * s[i] * v0) % mod) % mod;
if (i) {
v0 = (v0 * v) % mod;
}
}
}
void next(char r, char a)
{
val = (((val - (1ll * r * v0) % mod + mod) * v) % mod + a) % mod;
}
};
char a[2000001], b[2000001];
long long l1, l2;
int val[1001], nr;
int main()
{
fin >> b >> a;
l1 = strlen(b);
l2 = strlen(a);
Hash b1(31, 40099, l1), b2(53, 319993, l1);
Hash a1(31, 40099, l1), a2(53, 319993, l1);
b1.init(b);
b2.init(b);
a1.init(a);
a2.init(a);
if (b1.val == a1.val && b2.val == a2.val) {
val[nr++] = 0;
}
for (long long i = l1; i < l2; i++) {
a1.next(a[i - l1], a[i]);
a2.next(a[i - l1], a[i]);
if (b1.val == a1.val && b2.val == a2.val) {
if (nr <= 1000) {
val[nr++] = i - l1 + 1;
} else {
nr++;
}
}
}
fout << nr << '\n';
nr = min(nr, 1000);
for (int i = 0; i < nr; i++) {
fout << val[i] << " ";
}
}