CF1314G解题报告

题意

给定数组(p)和两个串(s)和(t)，(|s|ge|t|)，我们称(s')和(t)是相等的当且仅当(forall iin[0,len(t)),t_i=s'_i or t_i=p_{s'_i})，问对于(s)每一个位置开始的长度为(len(t))的子串是否与(t)相等。

(|s|,|t|le2*10^5)

题解

对于双字符串匹配(KMP)不能用的情况下，一般是(FFT)。

对于此题，如果(sum_{j=0}^{m-1}(t_j-s_{i+j})^2(t_j-p_{s_{i+j}})^2=0)则说明(t)与(s)在(i)位置上匹配了。

展开得到(t_j^4+(-2p_{s_{i+j}}-2s_{i+j})t_j^3+(p_{s_{i+j}}^2+4s_{i+j}p_{s_{i+j}}+s_{i+j}^2)t_j^2\+(-2s_{i+j}p_{s_{i+j}}^2-2s_{i+j}^2p_{s_{i+j}})t_j+s_{i+j}^2p_{s_{i+j}}^2)，观察到这个式子实际上是关于(s)和(t)的卷积，考虑将(s)或(t)翻转（考虑最后输出答案，我们选择翻转(t)），那么这个求和就是一个卷积的形式，可以快速用(FFT)求出。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define Mp make_pair
#define pb push_back
using namespace std;

using ll = long long;
using db = double;
using pii = pair<int, int>;
using vi = vector<int>;

-----ntt板子-----

const int P = 998244353, N = 2e5 + 100;
int n, m, val[30], p[30], s_[5][N], t_[5][N], ans[N]; char s[N], t[N];
signed main(){
	// freopen("data.in", "r", stdin);
	// freopen("my.out", "w", stdout);
    srand(time(0));
	for(int i = 0; i < 26; i++) val[i] = (ll)rand * rand() % P; // 随机权值，降低出错概率
	for(int i = 0, q; i < 26; i++) scanf("%d", &q), p[q - 1] = i;
	scanf("%s%s", t, s); n = strlen(s), m = strlen(t);
	for(int i = 0; i < n; i++) {
		s[i] -= 'a';
		ll u = val[s[i]], v = val[p[s[i]]];
		s_[4][i] = 1;
		s_[3][i] = (-2 * v - 2 * u) % P;
		s_[2][i] = (v * v + 4 * u * v + u * u) % P;
		s_[1][i] = (-2 * u * v * v - 2 * u * u * v) % P;
		s_[0][i] = u * u%P * v%P * v % P;
	}

	// printf("s_:
");
	// for(int i = 0; i < 5; i++) {
	// 	printf("	%d:", i);
	// 	for(int j = 0; j < n; j++) printf("%d ", s_[i][j]);
	// 	puts("");
	// }
	// puts("----------------------");

	for(int i = 0; i < n; i++) for(int j = 0; j < 5; j++) if(s_[j][i] < 0) s_[j][i] += P;
	for(int i = 0; i < m; i++) {
		ll u = val[t[i] - 'a']; t_[0][i] = 1;
		for(int j = 1; j < 5; j++) t_[j][i] = t_[j - 1][i] * u % P;
	}
	// printf("s_:
");
	// for(int i = 0; i < 5; i++) {
	// 	printf("	%d:", i);
	// 	for(int j = 0; j < n; j++) printf("%d ", s_[i][j]);
	// 	puts("");
	// }
	// printf("t_:
");
	// for(int i = 0; i < 5; i++) {
	// 	printf("	%d:", i);
	// 	for(int j = 0; j < m; j++) printf("%d ", t_[i][j]);
	// 	puts("");
	// }
	for(int x = 0; x < 5; x++) {
		reverse(t_[x], t_[x] + m); // 翻转得到卷积，翻转t_防止结果逆序
		vi res = multiply(vi(s_[x], s_[x] + n), vi(t_[x], t_[x] + n));
		for(int i = m - 1; i < n; i++) ans[i] += res[i], ans[i] %= P;
	}
	for(int i = m - 1; i < n; i++) putchar(ans[i] ? '0' : '1'); putchar('
');
	fprintf(stderr, "time=%.4f
", (db)clock()/CLOCKS_PER_SEC);
	return 0;
	/* 取模直接除，爆零两行泪
	 * 不开ll见祖宗
	 */
}