第六集，想不到你这个浓眉大眼的都叛变革命了
题意：
给你两个只包含01的字符串S和T，问你在允许一次错误的情况下，T是否能成为S的子串
思路：
这个问题的解法挺多，我是用fft匹配的，也比较简单，针对0和1匹配两次，第一次针对0就是把S串和T串中等于0的位置都标记成1，然后reverse一个串后进行fft，如果这两个位置都是0，就会出现1*1=1的情况，代表有一个位置匹配上了，0这样做一次，1这样做一次，他们的和就是匹配成功的次数，所以允许一次错误就是判断和是否大于len-1。
还有一个做法是指数哈希，判断两个串的哈希值的差是否是2^n，如果是的话check一下，就做出来了，2^n可以塞到hash或者map里。
还有exkmp等其他做法你们自行了解一下
代码实现
给出fft的做法（我只写了fft）
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = ;
ll a[N],b[N];
const ll PMOD=(<<)+;
const ll PR=;
static ll qp[];
ll res[N];
struct NTT__container
{
NTT__container()
{
int t,i;
for( i=; i<; i++)///注意循环上界与2n次幂上界相同
{
t=<<i;
qp[i]=quick_pow(PR,(PMOD-)/t);
}
}
ll quick_pow(ll x,ll n)
{
ll ans=;
while(n)
{
if(n&)
ans=ans*x%PMOD;
x=x*x%PMOD;
n>>=;
}
return ans;
}
int get_len(int n)///计算刚好比n大的2的N次幂
{
int i,len;
for(i=(<<); i; i>>=)
{
if(n&i)
{
len=(i<<);
break;
}
}
return len;
}
inline void NTT(ll F[],int len,int type)
{
int id=,h,j,k,t,i;
ll E,u,v;
for(i=,t=; i<len; i++)
{
if(i>t) swap(F[i],F[t]);
for(j=(len>>); (t^=j)<j; j>>=);
}
for( h=; h<=len; h<<=)
{
id++;
for( j=; j<len; j+=h)
{
E=;
for(int k=j; k<j+h/; k++)
{
u=F[k];
v=(E*F[k+h/])%PMOD;
F[k]=(u+v)%PMOD;
F[k+h/]=((u-v)%PMOD+PMOD)%PMOD;
E=(E*qp[id])%PMOD;
}
}
}
if(type==-)
{
int i;
ll inv;
for(i=; i<len/; i++)
swap(F[i],F[len-i]);
inv=quick_pow(len,PMOD-);
for( i=; i<len; i++)
F[i]=(F[i]%PMOD*inv)%PMOD;
}
}
inline void inv(ll *a,int len)///答案存在res中
{
if(len==)
{
res[]=quick_pow(a[],PMOD-);
return ;
}
inv(a,len>>);///递归
static ll temp[N];
memcpy(temp,a,sizeof(ll)*(len>>));
NTT(temp,len,);
NTT(res,len,);
int i;
for(i=; i<len; i++)
res[i]=res[i]*(-temp[i]*res[i]%PMOD+PMOD)%PMOD;
NTT(res,len,-);
memset(res+(len>>),,sizeof(ll)*(len>>));
}
void mul(ll x[],ll y[],int len)///答案存在x中
{
int i;
NTT(x,len,);///先映射到频域上
NTT(y,len,);///先映射到频域上
for(i=; i<len; i++)
x[i]=(x[i]*y[i])%PMOD;///在频域上点积
NTT(x,len,-);///再逆变换回时域
}
} cal;
ll x[N],y[N],z[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int N;
cin>>N;
while(N--){
string s1,s2;
cin>>s1>>s2;
if(s2.length()>s1.length()){
puts("NO");
continue;
}
int len=cal.get_len(s1.length());
//做1匹配
memset(x,,len*sizeof(ll));
memset(y,,len*sizeof(ll));
memset(z,,len*sizeof(ll));
for(int i=;i<s1.length();i++){
x[i]=s1[i]-'';
}
for(int i=;i<s2.length();i++){
y[i]=s2[i]-'';
}
reverse(y,y+s2.length());
cal.mul(x,y,len);
//for(int i=0;i<len;i++)
for(int i=s2.length()-;i<s1.length();i++)
z[i]+=x[i];
//做0匹配
memset(x,,len*sizeof(ll));
memset(y,,len*sizeof(ll));
for(int i=;i<s1.length();i++){
x[i]=-(s1[i]-'');
}
for(int i=;i<s2.length();i++){
y[i]=-(s2[i]-'');
}
reverse(y,y+s2.length());
cal.mul(x,y,len);
//for(int i=0;i<len;i++)
for(int i=s2.length()-;i<s1.length();i++)
z[i]+=x[i];
bool flag=;
for(int i=s2.length()-;i<s1.length();i++){
if(z[i]>=s2.length()-){
flag=;
break;
}
}
if(flag){
puts("YES");
}
else {
puts("NO");
}
}
}