省队集训Day1残缺的字符串

# include
# include
# include <string.h>
# include
# include
// # include
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 5e5 + 10, N = 2e6 + 10;
const int mod = 1e9+7;
const ld pi = acos(-1.0);
char s[M], t[M];
int A[M], B[M], ns, nt;
struct cp {
ld x, y;
cp() {}
cp(ld x, ld y) : x(x), y(y) {}
friend cp operator + (cp a, cp b) {
return cp(a.x + b.x, a.y + b.y);
}
friend cp operator - (cp a, cp b) {
return cp(a.x - b.x, a.y - b.y);
}
friend cp operator * (cp a, cp b) {
return cp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
}a[N], b[N], ans[N];
namespace FFT {
int n, lst[N]; cp w[2][N];
inline void set(int _n) {
n = 1;
while(n <_n) n <<= 1;
for (int i=0; i0][i] = cp(cos(pi * 2 / n * i), sin(pi * 2 / n * i)), w[1][i] = cp(w[0][i].x, -w[0][i].y);
int len = 0;
while((1<len;
for (int i=0; ii) {
int t = 0;
for (int j=0; jif(i & (1<1<<(len-j-1));
lst[i] = t;
}
}
inline void DFT(cp *a, int op) {
cp *o = w[op];
for (int i=0; iif(i < lst[i]) swap(a[i], a[lst[i]]);
for (int len=2; len<=n; len<<=1) {
int m = len>>1;
for (cp *p=a; p!=a+n; p+=len) {
for (int k=0; kk) {
cp t = o[n/len*k] * p[k+m];
p[k+m] = p[k] - t;
p[k] = p[k] + t;
}
}
}
if(op) {
for (int i=0; i (ld)n;
}
}
}
# define L FFT::n
int main() {
scanf("%s%s", t, s); ns = strlen(s), nt = strlen(t);
for (int i=0; i‘*‘ ? 0 : s[i] - ‘a‘ + 1);
for (int i=0; i‘*‘ ? 0 : t[i] - ‘a‘ + 1);
reverse(B, B+nt);
// (A[i] - B[i])^2 * A[i] * B[i] = A[i]^3 * B[i] + A[i] * B[i]^3 - A[i]^2 * B[i]^2
FFT :: set(max(ns, nt));
for (int i=0; i0);
for (int i=ns; i0, 0);
for (int i=0; i0);
for (int i=nt; i0, 0);
FFT :: DFT(a, 0); FFT :: DFT(b, 0);
for (int i=0; i b[i];
for (int i=0; i0);
for (int i=ns; i0, 0);
for (int i=0; i0);
for (int i=nt; i0, 0);
FFT :: DFT(a, 0); FFT :: DFT(b, 0);
for (int i=0; i b[i];
for (int i=0; i2, 0);
for (int i=ns; i0, 0);
for (int i=0; i0);
for (int i=nt; i0, 0);
FFT :: DFT(a, 0); FFT :: DFT(b, 0);
for (int i=0; i b[i];
FFT :: DFT(ans, 1);
for (int i=nt-1; ii) {
if((int)(ans[i].x-0.5) == 0) printf("%d ", i-nt+2);
}
puts("");
return 0;
}