Pagini recente » Istoria paginii jc2021/solutii/aglet | Denis S | Cod sursa (job #554016) | Cod sursa (job #1586074) | Cod sursa (job #3037831)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
const int NMAX = 2e6;
using ull = unsigned long long;
const ull P = 13331;
ull r[256];
ull hsh2[NMAX + 5];
ull p[NMAX + 5];
int main()
{
p[0] = 1;
for (int i=1; i<=NMAX; i++)
p[i] = p[i-1] * P;
for (int i=0; i<256; i++)
r[i] = (ull) rand() * rand() * rand() * rand();
string a, b;
in >> a >> b;
a = '$' + a;
b = '$' + b;
int n = (int)a.size() - 1;
int m = (int)b.size() - 1;
ull hsh1 = 0;
for (int i=1; i<=n; i++)
hsh1 = hsh1 * P + r[a[i]];
for (int i=1; i<=m; i++)
hsh2[i] = hsh2[i-1] * P + r[b[i]];
vector<int>ans;
for (int i=n; i<=m; i++)
{
if (hsh1 == hsh2[i] - hsh2[i-n] * p[n])
{
if (ans.size() < 1000)
ans.push_back(i-n);
else
break;
}
}
out << ans.size() << '\n';
for (int x : ans)
out << x << ' ';
return 0;
}