1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
#include <bits/stdc++.h>
const int OUT_LEN = 1000000;
char obuf[OUT_LEN], *oh = obuf;
char cntbuf[20], *cbh = cntbuf;
inline void print(char c) {
if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
*oh++ = c;
}
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) {
print('0');
} else {
if (x < 0) print('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) print((char)buf[cnt--]);
}
}
template<class T>
inline void printCount(T x) {
static int buf[30], cnt;
if (x == 0) {
*cbh++ = 48;
} else {
if (x < 0) *cbh++ = '-', x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) *cbh++ = buf[cnt--];
}
}
inline void flush() {
*cbh++ = '\n';
fwrite(cntbuf, 1, cbh - cntbuf, stdout);
fwrite(obuf, 1, oh - obuf, stdout);
}
const int MAXN = 100000;
struct Complex {
double r, i;
Complex(double r = 0, double i = 0) : r(r), i(i) {}
inline Complex operator + (const Complex &x) {
return Complex(r + x.r, i + x.i);
}
inline Complex operator - (const Complex &x) {
return Complex(r - x.r, i - x.i);
}
inline Complex operator * (const Complex &x) {
return Complex(r * x.r - i * x.i, r * x.i + i * x.r);
}
inline Complex conj() {
return Complex(r, -i);
}
} a[MAXN << 2], b[MAXN << 2];
const double PI = acos(-1);
int pos[MAXN << 2];
inline void fft(Complex *a, const int n, const int f) {
for (register int i = 1; i < n; i++) if (i < pos[i]) std::swap(a[i], a[pos[i]]);
for (register int i = 1; i < n; i <<= 1) {
double r = cos(PI / i), img = f * sin(PI / i);
Complex wn(r, img);
for (register int j = 0; j < n; j += i << 1) {
Complex w(1, 0);
Complex x, y;
for (register int k = 0; k < i; k++, w = w * wn)
a[j + k] = (x = a[j + k]) + (y = w * a[i + j + k]), a[i + j + k] = x - y;
}
}
if (f == -1) for (register int i = 0; i < n; i++) a[i].r /= n;
}
char s[MAXN + 10], t[MAXN + 10];
Complex A[MAXN << 2], B[MAXN << 2], C[MAXN << 2];
int lent, lens;
inline void solve() {
static int a[MAXN << 2], b[MAXN << 2];
for (register int i = 0; i < lens; i++) a[i] = s[i] - 'a' + 1;
for (register int i = 0; i < lent; i++) b[lent - i - 1] = t[i] == '?' ? 0 : t[i] - 'a' + 1;
register int k, len;
for (k = 1, len = 0; k < lens; k <<= 1, len++);
k <<= 1, len++;
for (register int i = 1; i < k; i++) pos[i] = (i & 1) ?
(pos[i >> 1] >> 1) ^ (k >> 1) : pos[i >> 1] >> 1;
for (register int i = 0; i < k; i++) A[i].r = b[i] * b[i] * b[i], B[i].r = 1;
fft(A, k, 1), fft(B, k, 1);
for (register int i = 0; i < k; i++) C[i] = A[i] * B[i];
for (register int i = 0; i < k; i++) A[i] = Complex(a[i] << 1, 0);
for (register int i = 0; i < k; i++) B[i] = Complex(b[i] * b[i], 0);
fft(A, k, 1), fft(B, k, 1);
for (register int i = 0; i < k; i++) C[i] = C[i] - A[i] * B[i];
for (register int i = 0; i < k; i++) A[i] = Complex(a[i] * a[i], 0);
for (register int i = 0; i < k; i++) B[i] = Complex(b[i], 0);
fft(A, k, 1), fft(B, k, 1);
for (register int i = 0; i < k; i++) C[i] = C[i] + A[i] * B[i];
fft(C, k, -1);
register int num = 0;
for (register int i = 0; i <= lens - lent; i++)
if (C[i + lent - 1].r < 0.5)
print(i), print('\n'), num++;
printCount(num);
}
int main() {
scanf("%s\n%s", s, t);
lens = strlen(s), lent = strlen(t);
solve();
flush();
return 0;
}
|
