```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1100010;
const double pi = acos (-1.0);
typedef complex <double> comp;
const comp I (0.0, 1.0);
int rgt[N];
void dft (vector <comp>& a, int inv) {
int n = a.size ();
for (int i = 0; i < n; i++) {
if (i < rgt[i]) {
swap (a[i], a[rgt[i]]);
}
}
for (int mid = 1; mid < n; mid <<= 1) {
comp wn (cos (pi / mid), inv * sin (pi / mid));
for (int i = 0; i < n; i += mid << 1) {
comp w = 1.0;
for (int j = 0; j < mid; j++) {
comp x = a[i + j], y = w * a[i + j + mid];
a[i + j] = x + y;
a[i + j + mid] = x - y;
w *= wn;
}
}
}
if (inv == -1) {
for (int i = 0; i < n; i++) {
a[i] /= n;
}
}
}
int n, m;
char a[N], b[N];
vector <comp> f, g, t1, t2, t3, t4, ans;
int main () {
scanf ("%d%d%s%s", &m, &n, b, a);
int k = 0;
for (; (1 << k) <= m + n; ++k);
for (int i = 0; i < (1 << k); ++i) {
rgt[i] = (rgt[i >> 1] >> 1) | ((i & 1) << (k - 1));
}
f.resize (1 << k);
g.resize (1 << k);
t1.resize (1 << k);
t2.resize (1 << k);
t3.resize (1 << k);
t4.resize (1 << k);
ans.resize (1 << k);
reverse (a, a + n);
for (int i = 0; i < n; i++) {
if (a[i] != '*') {
f[i] = comp (a[i] - 'a' + 1, 0);
}
}
for (int i = 0; i < m; i++) {
if (b[i] != '*') {
g[i] = comp (b[i] - 'a' + 1, 0);
}
}
for (int i = 0; i < (1 << k); i++) {
t1[i] = f[i] * f[i] * f[i];
t2[i] = g[i];
}
dft (t1, 1);
dft (t2, 1);
for (int i = 0; i < (1 << k); i++) {
ans[i] += t1[i] * t2[i];
}
for (int i = 0; i < (1 << k); i++) {
t3[i] = g[i] * g[i] * g[i];
t4[i] = f[i];
}
dft (t3, 1);
dft (t4, 1);
for (int i = 0; i < (1 << k); i++) {
ans[i] += t3[i] * t4[i];
}
for (int i = 0; i < (1 << k); i++) {
f[i] = f[i] * f[i];
g[i] = g[i] * g[i];
}
dft (f, 1);
dft (g, 1);
for (int i = 0; i < (1 << k); i++) {
ans[i] -= 2. * f[i] * g[i];
}
dft (ans, -1);
vector <int> tot;
for (int i = m - 1; i < n; i++) {
if (fabs (ans[i].real ()) < 0.1) {
tot.push_back (i - m + 2);
}
}
printf ("%d\n", tot.size ());
for (int i = 0; i < tot.size (); i++) {
printf ("%d%c", tot[i], " \n"[i == tot.size ()]);
}
return 0;
}
```
by denominator @ 2024-01-28 20:25:14