CF1334G Substring Search FFT在字符串匹配上的应用

题意

给定小串\(t\),长串\(s\)

定义小串中的\(t_i\)与长串中的\(s_{j+i}\)匹配当且仅当如下两个条件任意一个成立

1.\(t_i = s_{j+i}\)

2.\(s_{i+j} = p_{t_i}\)

其中\(p\)是对\(t\)的一个映射，比如\(p_a = b\)也就是说\(t\)中的\(a\)在匹配时可以被认为是\(b\)，但是\(s\)中的\(a\)不行

分析

为了做题方便，先做一下转化，对题目给定的映射求反函数，这样就变成了\(t\)固定，\(s\)中的字符可以变

对于字符串匹配的问题通常优先考虑KMP，但是此题的映射操作不满足等价关系，没办法做出等于的判断

对于没办法KMP的题目，一般考虑FFT

FFT可以在\(O(lenloglen)\)的时间里解决字符串匹配问题

它的思想是定义匹配字符的匹配函数\(match(j) = (s[j + i] - t[i])^2\)

如果\(match(j) =0\)表面\(j\)这个位置匹配 这显然是成立的，对应到连续的一段，可以定义为

\(M(j) = \sum_{i=0}^{m-1} (s[j+i] - t[i])^2\) 这也是要开平方的原因

那么将这个二项式展开以后，对\(t\)反转，就可以发现出现了卷积的形式，对\(t‘\)和\(s\)卷积以后，只需询问对应位置是否为零即可

拓展到这题，我们直需改写匹配函数 ：发现两者是或的关系，于是只需要把两个式子乘起来

\(M(j) = \sum_{i=0}^{m-1}(s[j + i] - t[i])^2 (t[i] - p[s_{j+i}])^2\)

将上式展开以后跑FFT/NTT即可

代码

通过dls代码学到的技巧：由于NTT可以看出值域上的Hash，这里最好是用FFT解决，但是FFT采用浮点运算，速度和精度都不及NTT，因此可以对每个字母随机一个权值，然后再跑NTT即可

反思：调BUG调了许久，发现由于多个地方涉及取模操作，因此不妨写长一点的代码，对于多次乘的时候，可以写个mul函数来简化

#include
#define pii pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
const int MOD = 998244353;
ll rd(){
ll x = 0;
char ch = getchar();
while(ch <‘0‘ || ch > ‘9‘){
ch = getchar();
}
while(ch >= ‘0‘ && ch <= ‘9‘){
x = x * 10 + ch - ‘0‘;
ch = getchar();
}
return x;
}
inline void add(int &x,int y){
x += y;
if(x >= MOD)
x -= MOD;
}
inline void sub(int &x,int y){
x -= y;
if(x <0)
x += MOD;
}
inline int mul(int x,int y){
return (ll)x * y % MOD;
}
inline int ksm(int a,int b = MOD - 2,int m = MOD){
int ans = 1;
int base = a;
while(b){
if(b & 1) ans = (ll)ans * base % MOD;
base = (ll)base * base % MOD;
b >>= 1;
}
return ans;
}
class NTTClass{
public:
static const int MAXL= 21;
static const int MAXN= 1 < static const int root= 3;
static const int MOD= 998244353;
int rev[MAXN];

inline int fast_pow(int a,int b){
int ans=1;
while(b){
if(b & 1) ans = 1ll * ans * a %MOD;
a = (ll)a * a %MOD;
b >>= 1;
}
return ans;
}

inline void transform(int n,int *t,int typ){
for(int i = 0;i if(i for(int step = 1;step int gn = fast_pow(root,(MOD - 1)/(step <<1));
for(int i = 0;i int g = 1;
for(int j = 0;j int x = t[i + j],y = (ll)g * t[i + j + step] % MOD;
t[i + j] = (x + y)% MOD;
t[i + j + step]=(x - y + MOD)%MOD;
}
}
}
if(typ == 1)return;
for(int i = 1;i int inv = fast_pow(n,MOD - 2);
for(int i = 0;i }

inline void ntt(int p,int *A,int *B,int *C){
transform(p,A,1);
transform(p,B,1);
for(int i = 0;i transform(p,C,-1);
}

inline void mul(int *A,int *B,int *C,int n,int m) {
int p = 1,l = 0;
while(p <= n + m)p <<= 1,l++;
//printf("n = %d, m = %d\n",n,m);
for (int i = n + 1;i for (int i = m + 1;i //for (int i=0;i //for (int i=0;i for(int i = 0;i > 1] >> 1) | ((i & 1) <<(l - 1));
ntt(p,A,B,C);
//puts("C:");for (int i=0;i }
}NTT;
const int maxn = 2e5 +5;
char s[maxn],t[maxn];
int val[maxn];
int a[maxn * 3],b[maxn * 3],c[maxn * 3];
int C[maxn * 3];
int sum[maxn];
int p[30];
inline int get(char ch){
int res = val[ch - ‘a‘];
res = mul(res,res);
res = mul(res,res);
return res;
}
int main(){
for(int i = 0;i <26;i++)
val[i] = rnd() % MOD;
for(int i = 0;i <26;i++)
p[rd() - 1] = i;
scanf("%s %s",t,s);
int sumT = 0;
int n = strlen(s);
int m = strlen(t);
reverse(t,t + m);
for(int i = 0;i add(sumT,get(t[i]));
sum[0] = mul(val[s[0] - ‘a‘],mul(val[s[0] - ‘a‘],mul(val[p[s[0] - ‘a‘]],val[p[s[0] - ‘a‘]])));
for(int i = 1;i sum[i] = sum[i - 1],add(sum[i],(mul(val[s[i] - ‘a‘],mul(val[s[i] - ‘a‘],mul(val[p[s[i] - ‘a‘]],val[p[s[i] - ‘a‘]])))));
for(int i = 0;i a[i] = (val[p[s[i] - ‘a‘]] + val[s[i] - ‘a‘]) % MOD;
for(int i = 0;i b[i] = mul(val[t[i] - ‘a‘],mul(val[t[i] - ‘a‘],val[t[i] - ‘a‘]));
NTT.mul(a,b,c,n - 1,m - 1);
for(int i = 0;i add(C[i],(ll)2 * c[i] % MOD);

for(int i = 0;i int add1 = mul(val[s[i] - ‘a‘] , val[s[i] - ‘a‘]);
int add2 = mul(val[s[i] - ‘a‘] , val[p[s[i] - ‘a‘]]);
add2 = mul(4,add2);
int add3 = mul(val[p[s[i] - ‘a‘]],val[p[s[i] - ‘a‘]]);
a[i] = add1;
add(a[i],add2);
add(a[i],add3);
}
for(int i = 0;i b[i] = (ll)val[t[i] - ‘a‘] * val[t[i] - ‘a‘] % MOD;
NTT.mul(a,b,c,n - 1,m - 1);
for(int i = 0;i sub(C[i],c[i]);
for(int i = 0;i int add1 = val[s[i] - ‘a‘] + val[p[s[i] - ‘a‘]] % MOD;
a[i] = mul(add1,mul(val[s[i] - ‘a‘],val[p[s[i] - ‘a‘]]));
}
for(int i = 0;i b[i] = val[t[i] - ‘a‘];
NTT.mul(a,b,c,n - 1,m - 1);
for(int i = 0;i add(C[i],(ll)2 * c[i] % MOD);
for(int i = m - 1;i // cout <// cout <<(sumT + (MOD + sum[i] - (i if(C[i] == (ll)(sumT + (MOD + sum[i] - (i - m <0 ? 0 : sum[i - m])) % MOD) % MOD) putchar(‘1‘);
else putchar(‘0‘);
}
}