嘟嘟嘟
如题，FFT残缺字符串匹配。
简单来说，就是定义一个匹配函数，然后稍稍推一下柿子。
细节来不及写了，推荐luogu的第一篇题解，讲的特别好。
（没事别开long double，这东西慢的很）
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 3e5 + 5;
const int maxN = 1.1e6 + 5;
const db PI = acos(-1);
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen("ha.in", "r", stdin);
freopen("ha.out", "w", stdout);
#endif
}
int n, m;
char a1[maxn], b1[maxn];
int len = 1, lim = 0, rev[maxN];
struct Comp
{
db x, y;
In Comp operator + (const Comp& oth)const
{
return (Comp){x + oth.x, y + oth.y};
}
In Comp operator - (const Comp& oth)const
{
return (Comp){x - oth.x, y - oth.y};
}
In Comp operator * (const Comp& oth)const
{
return (Comp){x * oth.x - y * oth.y, x * oth.y + y * oth.x};
}
friend In void swap(Comp& A, Comp& B)
{
swap(A.x, B.x), swap(A.y, B.y);
}
}A[maxN], B[maxN], ans[maxN];
In void fft(Comp* a, int len, int flg)
{
for(int i = 0; i < len; ++i) if(i < rev[i]) swap(a[i], a[rev[i]]);
for(int i = 1; i < len; i <<= 1)
{
Comp omg = (Comp){cos(PI / i), sin(PI / i) * flg};
for(int j = 0; j < len; j += (i << 1))
{
Comp o = (Comp){1, 0};
for(int k = 0; k < i; ++k, o = o * omg)
{
Comp tp1 = a[j + k], tp2 = a[j + k + i] * o;
a[j + k] = tp1 + tp2, a[j + k + i] = tp1 - tp2;
}
}
}
}
int a[maxn], b[maxn];
In void fftMatch()
{
reverse(a1, a1 + m);
for(int i = 0; i < m; ++i) a[i] = a1[i] == '*' ? 0 : a1[i] - 'a' + 1;
for(int i = 0; i < n; ++i) b[i] = b1[i] == '*' ? 0 : b1[i] - 'a' + 1;
while(len < n + n) len <<= 1, ++lim;
for(int i = 0; i < len; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lim - 1));
for(int i = 0; i < len; ++i)
{
A[i] = (Comp){i < m ? a[i] * a[i] * a[i] : 0, 0};
B[i] = (Comp){i < n ? b[i] : 0, 0};
}
fft(A, len, 1), fft(B, len, 1);
for(int i = 0; i < len; ++i) ans[i] = ans[i] + A[i] * B[i];
for(int i = 0 ; i < len; ++i)
{
A[i] = (Comp){i < m ? a[i] * a[i] : 0, 0};
B[i] = (Comp){i < n ? b[i] * b[i] : 0, 0};
}
fft(A, len, 1), fft(B, len, 1);
for(int i = 0; i < len; ++i) ans[i] = ans[i] - A[i] * B[i] * (Comp){2, 0};
for(int i = 0; i < len; ++i)
{
A[i] = (Comp){i < m ? a[i] : 0, 0};
B[i] = (Comp){i < n ? b[i] * b[i] * b[i]: 0, 0};
}
fft(A, len, 1), fft(B, len, 1);
for(int i = 0; i < len; ++i) ans[i] = ans[i] + A[i] * B[i];
fft(ans, len, -1);
}
int Ans[maxn], tot = 0;
int main()
{
// MYFILE();
m = read(), n = read();
scanf("%s%s", a1, b1);
fftMatch();
for(int i = m - 1; i < n; ++i)
if(!((ll)(ans[i].x / len + 0.5))) Ans[++tot] = i - m + 2;
write(tot), enter;
if(tot) {for(int i = 1; i <= tot; ++i) write(Ans[i]), space; enter;}
return 0;
}