Pagini recente » Cod sursa (job #311572) | Cod sursa (job #387023) | Cod sursa (job #2762418) | Cod sursa (job #679165) | Cod sursa (job #3228362)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
using ftype = complex<double>;
ftype root(double ang) {
return ftype(cos(ang), sin(ang));
}
void ntt(vector <ftype> &a, bool rev) {
int n = a.size();
auto b = a;
for(int step = n / 2; step > 0; step /= 2) {
for(int i = 0; i < n / 2; i += step) {
ftype wn = root(2 * M_PI * i * (rev ? -1 : 1) / n);
for(int j = 0; j < step; j++) {
ftype u = a[2 * i + j], v = wn * a[2 * i + j + step];
b[i + j] = (u + v);
b[i + j + n / 2] = (u - v);
}
}
swap(a, b);
}
if(rev) {
for(auto& x: a) {
x /= n;
}
}
}
void fastMult(vector<ftype> &a, vector<ftype> &b) {
int n = a.size() + b.size();
int p = 1;
while(p < n) {
p *= 2;
}
n = p;
a.resize(n);
b.resize(n);
ntt(a, 0);
ntt(b, 0);
for(int i = 0; i < n; i++) {
a[i] *= b[i];
}
ntt(a, 1);
}
int main() {
string p, t;
fin >> p >> t;
reverse(p.begin(), p.end());
int n = p.size(), m = t.size();
if(n > m) {
fout << "0\n";
} else {
vector<ftype> a(m), b(m);
int sum1 = 0;
for(int i = 0; i < n; i++) {
a[i] = p[i];
sum1 += p[i] * p[i];
}
vector<int> sp(m + 1);
for(int i = 0; i < m; i++) {
b[i] = t[i];
sp[i + 1] = t[i] * t[i] + sp[i];
}
fastMult(a, b);
int cnt = 0;
vector<int> ans;
for(int i = n - 1; i < m; i++) {
int sum2 = sp[i + 1] - sp[i - n + 1];
if(sum1 - 2 * round(a[i].real()) + sum2 == 0) {
cnt++;
if(cnt <= 1000) {
ans.emplace_back(i - n + 1);
}
}
}
fout << cnt << '\n';
for(const auto &it: ans) {
fout << it << " ";
}
}
return 0;
}