第六集, 想不到你这个浓眉大眼的都叛变革命了
题意:
给你两个只包含 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 = 150000;
- ll a[N],b[N];
- const ll PMOD=(479<<21)+1;
- const ll PR=3;
- static ll qp[30];
- ll res[N];
- struct NTT__container
- {
- NTT__container()
- {
- int t,i;
- for( i=0; i<21; i++)/// 注意循环上界与 2n 次幂上界相同
- {
- t=1<<i;
- qp[i]=quick_pow(PR,(PMOD-1)/t);
- }
- }
- ll quick_pow(ll x,ll n)
- {
- ll ans=1;
- while(n)
- {
- if(n&1)
- ans=ans*x%PMOD;
- x=x*x%PMOD;
- n>>=1;
- }
- return ans;
- }
- int get_len(int n)/// 计算刚好比 n 大的 2 的 N 次幂
- {
- int i,len;
- for(i=(1<<30); i; i>>=1)
- {
- if(n&i)
- {
- len=(i<<1);
- break;
- }
- }
- return len;
- }
- inline void NTT(ll F[],int len,int type)
- {
- int id=0,h,j,k,t,i;
- ll E,u,v;
- for(i=0,t=0; i<len; i++)
- {
- if(i>t) swap(F[i],F[t]);
- for(j=(len>>1); (t^=j)<j; j>>=1);
- }
- for( h=2; h<=len; h<<=1)
- {
- id++;
- for( j=0; j<len; j+=h)
- {
- E=1;
- for(int k=j; k<j+h/2; k++)
- {
- u=F[k];
- v=(E*F[k+h/2])%PMOD;
- F[k]=(u+v)%PMOD;
- F[k+h/2]=((u-v)%PMOD+PMOD)%PMOD;
- E=(E*qp[id])%PMOD;
- }
- }
- }
- if(type==-1)
- {
- int i;
- ll inv;
- for(i=1; i<len/2; i++)
- swap(F[i],F[len-i]);
- inv=quick_pow(len,PMOD-2);
- for( i=0; i<len; i++)
- F[i]=(F[i]%PMOD*inv)%PMOD;
- }
- }
- inline void inv(ll *a,int len)/// 答案存在 res 中
- {
- if(len==1)
- {
- res[0]=quick_pow(a[0],PMOD-2);
- return ;
- }
- inv(a,len>>1);/// 递归
- static ll temp[N];
- memcpy(temp,a,sizeof(ll)*(len>>1));
- NTT(temp,len,1);
- NTT(res,len,1);
- int i;
- for(i=0; i<len; i++)
- res[i]=res[i]*(2-temp[i]*res[i]%PMOD+PMOD)%PMOD;
- NTT(res,len,-1);
- memset(res+(len>>1),0,sizeof(ll)*(len>>1));
- }
- void mul(ll x[],ll y[],int len)/// 答案存在 x 中
- {
- int i;
- NTT(x,len,1);/// 先映射到频域上
- NTT(y,len,1);/// 先映射到频域上
- for(i=0; i<len; i++)
- x[i]=(x[i]*y[i])%PMOD;/// 在频域上点积
- NTT(x,len,-1);/// 再逆变换回时域
- }
- } cal;
- ll x[N],y[N],z[N];
- int main()
- {
- iOS::sync_with_stdio(false);
- cin.tie(0);
- 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,0,len*sizeof(ll));
- memset(y,0,len*sizeof(ll));
- memset(z,0,len*sizeof(ll));
- for(int i=0;i<s1.length();i++){
- x[i]=s1[i]-'0';
- }
- for(int i=0;i<s2.length();i++){
- y[i]=s2[i]-'0';
- }
- reverse(y,y+s2.length());
- cal.mul(x,y,len);
- //for(int i=0;i<len;i++)
- for(int i=s2.length()-1;i<s1.length();i++)
- z[i]+=x[i];
- // 做 0 匹配
- memset(x,0,len*sizeof(ll));
- memset(y,0,len*sizeof(ll));
- for(int i=0;i<s1.length();i++){
- x[i]=1-(s1[i]-'0');
- }
- for(int i=0;i<s2.length();i++){
- y[i]=1-(s2[i]-'0');
- }
- reverse(y,y+s2.length());
- cal.mul(x,y,len);
- //for(int i=0;i<len;i++)
- for(int i=s2.length()-1;i<s1.length();i++)
- z[i]+=x[i];
- bool flag=0;
- for(int i=s2.length()-1;i<s1.length();i++){
- if(z[i]>=s2.length()-1){
- flag=1;
- break;
- }
- }
- if(flag){
- puts("YES");
- }
- else {
- puts("NO");
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3061491.html