【BZOJ4503】两个串（FFT）

题面

给定串\(S\),以及带通配符的串\(T\)，询问\(T\)在\(S\)中出现了几次。并且输出对应的位置。

\(|S|,|T|<=10^5\),字符集大小为\(26\)

题解

先来考虑没有通配符怎么匹配。~~别跟我说KMP！！~~

根据前面几个题目的套路，我们可以把每个字符分开来考虑，然后将\(T\)串反转，将有这个字符的位置变成\(1\)，然后\(FFT\)，就可以知道在这一段里面这个字符匹配上了多少个，然后把每个字符求个和，检查是否恰好匹配了\(|T|\)个。

通配符此时并不需要考虑。

时间复杂度\(O(26nlogn)\)

当然，如果您真的这么写了，那么肯定\(T\)飞了。\(FFT\)自带巨大常数。对于字符集很小的时候上述方法是可行的，字符集很大的时候就不能这么做了。

所以我们考虑如何只做一遍\(FFT\)。（没有通配符的情况下）

每个字符当然不能动了，所以把他们对应成数字。如果匹配上了怎么办？那就是上下两个对应的数字相等，可以考虑作差。但是又发现作差可能会使得几个正数和几个负数相加变成\(0\)，所以考虑平方。

所以，我们定义每个位置的函数值\(f(x)=\sum_{i=1}^{|T|}(S[x+i-1]-T[i])^2\)

将\(T\)串反转，平方项拆开之后，就变成了两个卷积+一个常数项的形式，直接\(FFT\)然后求和，检查最后的函数值是否为\(0\)就行了。

现在有了通配符，我们不妨令\(a..z\)对应的数字为\(1..26\)。通配符无论给它一个什么数字，它和上面的字符的差的平方一定不为\(0\)。

所以我们换种方法考虑，把通配符对应的数字设为\(0\)，但是这样差的平方不是\(0\)，所以我们就在上面那个式子后面乘上一个\(T[i]\)的权值，如果此时是通配符就会乘\(0\)，从而也变成了\(0\)。这样一来，原来的式子就变成了\(f(x)=\sum_{i=1}^{|T|}(S[x+i-1]-T[i])^2T[i]\)

拆开后是两个卷积+一个常数项的形式，\(FFT\)即可。

时间复杂度\(O(nlogn)\)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;#define ll long long#define RG register#define MAX 333333const double Pi=acos(-1);struct Complex{double a,b;}A1[MAX],B1[MAX],A2[MAX],B2[MAX],W[MAX],F[MAX];Complex operator+(Complex a,Complex b){return (Complex){a.a+b.a,a.b+b.b};}Complex operator-(Complex a,Complex b){return (Complex){a.a-b.a,a.b-b.b};}Complex operator*(Complex a,Complex b){return (Complex){a.a*b.a-a.b*b.b,a.a*b.b+a.b*b.a};}int n,m,r[MAX],N,Z;int pos[MAX],ans,l;char S[MAX],T[MAX];void FFT(Complex *P,int opt){ for(int i=1;i
              
               
                >1]>>1)|((i&1)<<(l-1)); for(int i=1;i
                
                 <<=1) for(int k=0;k

转载于:https://www.cnblogs.com/cjyyb/p/8798446.html

你可能感兴趣的文章