BZOJ 4503: 两个串

Description

兔子们在玩两个串的游戏。给定两个字符串S和T，兔子们想知道T在S中出现了几次，

分别在哪些位置出现。注意T中可能有“?”字符，这个字符可以匹配任何字符。

Input

两行两个字符串，分别代表S和T

Output

第一行一个正整数k，表示T在S中出现了几次

接下来k行正整数，分别代表T每次在S中出现的开始位置。按照从小到大的顺序输出，S下标从0开始。

Sample Input

ababcadaca

a?a

Sample Output

HINT

S 长度不超过 10^5， T 长度不会超过 S。 S 中只包含小写字母， T中只包含小写字母和“?”

Solution

我们将T翻转，并令c[j + m – 1] = sigma((a[j + i] – b[m – 1 -i]) ^ 2 * a[j + i] * b[m – 1 – i]) (0 <= i < m)
其中m为T的长度，a[i]表示S的第i个字符的(a视为1，b视为2，依次类推），b[i]为T的第i个字符，当T[i] = ‘?‘时，令b[i] = 0.
可以发现，c[j + m – 1] = 0当且仅当S从第j个位置开始可以匹配上T。于是计算出所有的c即可
注意到上式实际上是一个卷积，于是使用快速傅立叶变换(FFT)求解即可，时间复杂度O(nlgn)
————Vani

Let’s Orz……

Code

 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
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const double pi = acos(-1);
struct Complex {
	double x, y;
	Complex () { x = y = 0; }
	Complex (double a, double b) { x = a; y = b; }
	Complex operator + (Complex a) { return Complex(a.x + x, a.y + y); }
	Complex operator - (Complex a) { return Complex(x - a.x, y - a.y); }
	Complex operator * (Complex a) { return Complex(x * a.x - y * a.y, x * a.y + y * a.x); }
};
int n, R[433333];
void FFT(Complex *a, double f) {
	for (int i = 0; i < n; ++i) if (i < R[i]) swap(a[i], a[R[i]]);
	for (int i = 1; i < n; i <<= 1) {
		Complex wn(cos(pi / i), f * sin(pi / i));
		for (int j = 0; j < n; j += (i << 1)) {
			Complex w(1, 0);
			for (int k = 0; k < i; ++k){
				Complex x = a[j + k], y = a[i + j + k] * w;
				a[j + k] = x + y;
				a[j + k + i] = x - y;
				w = w * wn;
			}
		}
	}
	if (f == -1) for (int i = 0; i < n; ++i) a[i].x /= n;
}
char S[100005], T[100005];
typedef long long LL;
Complex A[433333], B[433333], C1[433333], C2[433333], C3[433333];
int slen, tlen;
LL F[433333], a[433333], b[433333];
int ans[433333], top = 0;
int main() {
	freopen("two.in", "r", stdin);
	freopen("two.out", "w", stdout);
	scanf("%s", S);
	scanf("%s", T);
	slen = strlen(S);
	tlen = strlen(T);
	for (int i = 0, j = tlen-1; i < j; ++i, --j) swap(T[i], T[j]);
	for (int i = 0; i < slen; ++i) a[i] = S[i] - 'a' + 1;
	for (int i = 0; i < tlen; ++i) b[i] = (T[i] == '?' ? 0 : T[i] - 'a' + 1);
	int L = 0, mx = slen * 2 - 1;
	for (n = 1; n <= mx; n <<=1) ++L;
	for (int i = 1; i < n; ++i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L-1));
	for (int i = 0; i < n; ++i) A[i].x = a[i]*a[i]*a[i], A[i].y = 0;
	for (int i = 0; i < n; ++i) B[i].x = b[i], B[i].y = 0;
	FFT(A, 1);
	FFT(B, 1);
	for (int i = 0; i < n; ++i) C1[i] = A[i] * B[i];
	FFT(C1, -1);
	for (int i = 0; i < n; ++i) A[i].x = a[i]*a[i], A[i].y = 0;
	for (int i = 0; i < n; ++i) B[i].x = b[i]*b[i], B[i].y = 0;
	FFT(A, 1);
	FFT(B, 1);
	for (int i = 0; i < n; ++i) C2[i] = A[i] * B[i];
	FFT(C2, -1);
	for (int i = 0; i < n; ++i) A[i].x = a[i], A[i].y = 0;
	for (int i = 0; i < n; ++i) B[i].x = b[i]*b[i]*b[i], B[i].y = 0;
	FFT(A, 1);
	FFT(B, 1);
	for (int i = 0; i < n; ++i) C3[i] = A[i] * B[i];
	FFT(C3, -1);
	for (int i = 0; i < n; ++i) F[i] = LL(C1[i].x+0.5)+LL(C3[i].x+0.5)-2*LL(C2[i].x+0.5);
	--tlen;
	for (int i = tlen; i < slen; ++i) if (F[i] == 0) ans[++top] = i-tlen;
	printf("%d\n", top);
	for (int i = 1; i <= top; ++i)
		printf("%d\n", ans[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}