4503: 两个串

题意：

　　求第二个串在第一个中出现了几次，用通配符。求出每个串的起始位置。

分析：

　　bitset。

　　一共有26个字母，求出每个字母在第一个串中出现的位置。扫一遍第二个串，ans = p[[1]] & (p[T[2]]>>1) & (p[T[3]>>3]) & ... & p[T[n]>>n]。很好理解，就是每个字符所有出现的位置往右移，如果匹配，那么这一位and后，为1。

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N = 200001;bitset
           
             p[26], ans;char s[N], t[N];int main() { scanf("%s", s); int l1 = strlen(s); scanf("%s", t); int l2 = strlen(t); for (int j=0; j<26; ++j) for (int i=0; i
            
             > i); } cout << ans.count() << "\n"; for (int i=0; i
            
           
          
         
        
       
      

 

 

FFT的做法：

如果T出现在S中，那么有$\sum\limits_{i=0}^{m-1} (S_i-T_i)^2=0$

如果出现通配符，如果T出现在S中，那么设T[i]=0，那么有$\sum\limits_{i=0}^{m-1} (S_i-T_i)^2 \times T[i]=0$

然后将式子拆开$\sum\limits_{i=0}^{m-1} S_i^2T_i-2S_iT_i^2+T_i^3=0$

把T翻转，然后FFT即可。

当然，这只是对应到第一个位置的情况，其他的情况类似只需要将卷积后的指数改一下即可。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include