Pagini recente » Cod sursa (job #2503268) | Cod sursa (job #3231337) | Cod sursa (job #1120054) | Cod sursa (job #2660181) | Cod sursa (job #3228359)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> add(vector<int> a, const vector<int> &b) {
a.resize(max(a.size(), b.size()));
for(int i = 0; i < (int)a.size(); i++) {
a[i] += i < (int)b.size() ? b[i] : 0;
}
return a;
}
vector<int> naiveMult(const vector<int> &a, const vector<int> &b) {
vector<int> res(2 * max(a.size(), b.size()) - 1);
for(int i = 0; i < (int)a.size(); i++) {
for(int j = 0; j < (int)b.size(); j++) {
res[i + j] += a[i] * b[j];
}
}
return res;
}
vector<int> fastMult(const vector<int> &a, const vector<int> &b) {
int n = a.size(), m = n / 2;
if(n <= 32) {
return naiveMult(a, b);
}
vector<int> a0(a.begin(), a.begin() + m), a1(a.begin() + m, a.end());
vector<int> b0(b.begin(), b.begin() + m), b1(b.begin() + m, b.end());
vector<int> sumA = add(a0, a1), sumB = add(b0, b1);
vector<int> a0b0 = fastMult(a0, b0), a1b1 = fastMult(a1, b1), sumMult = fastMult(sumA, sumB);
vector<int> res(2 * n - 1);
for(int i = 2 * m; i - 2 * m < (int)a1b1.size(); i++) {
res[i] += a1b1[i - 2 * m];
}
for(int i = m; i - m < (int)sumMult.size(); i++) {
res[i] += sumMult[i - m];
res[i] -= i - m < (int)a0b0.size() ? a0b0[i - m] : 0;
res[i] -= i - m < (int)a1b1.size() ? a1b1[i - m] : 0;
}
for(int i = 0; i < (int)a0b0.size(); i++) {
res[i] += a0b0[i];
}
return res;
}
int main() {
string p, t;
fin >> p >> t;
reverse(p.begin(), p.end());
int n = p.size(), m = t.size();
vector<int> a(m), b(m);
int sum1 = 0;
for(int i = 0; i < n; i++) {
a[i] = p[i];
sum1 += a[i] * a[i];
}
vector<int> sp(m + 1);
for(int i = 0; i < m; i++) {
b[i] = t[i];
sp[i + 1] = b[i] * b[i] + sp[i];
}
vector<int> c = 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 * c[i] + sum2 == 0) {
cnt++;
if(cnt <= 1000) {
ans.emplace_back(i - n + 1);
}
}
}
fout << cnt << '\n';
for(const auto &it: ans) {
fout << it << " ";
}
return 0;
}