Advertisement
RaFiN_

FFT

Sep 26th, 2019
288
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.56 KB | None | 0 0
  1. // sometimes u need to use long double .so be careful
  2.  typedef complex < double > base ;
  3.   const double PI = 2*acos( 0.0 );
  4.  
  5. void fft ( vector < base > & a, bool invert ) {
  6.     int n = ( int ) a. size ( ) ;
  7.  
  8.     for ( int i = 1 , j = 0 ; i < n ; ++ i ) {
  9.         int bit = n >> 1 ;
  10.         for ( ; j >= bit ; bit >>= 1 )
  11.             j -= bit ;
  12.         j += bit ;
  13.         if ( i < j )
  14.             swap ( a [ i ] , a [ j ] ) ;
  15.     }
  16.  
  17.     for ( int len = 2 ; len <= n ; len <<= 1 ) {
  18.         double ang = 2 * PI / len * ( invert ? - 1 : 1 ) ;
  19.         base wlen ( cos ( ang ) , sin ( ang ) ) ;
  20.         for ( int i = 0 ; i < n ; i += len ) {
  21.             base w ( 1 ) ;
  22.             for ( int j = 0 ; j < len / 2 ; ++ j ) {
  23.                 base u = a [ i + j ] ,  v = a [ i + j + len / 2 ] * w ;
  24.                 a [ i + j ] = u + v ;
  25.                 a [ i + j + len / 2 ] = u - v ;
  26.                 w *= wlen ;
  27.             }
  28.         }
  29.     }
  30.     if ( invert )
  31.         for ( int i = 0 ; i < n ; ++ i )
  32.             a [ i ] /= n ;
  33. }
  34.  
  35. void multiply ( const vector < ll > & a, const vector < ll > & b, vector < ll > & res ) {
  36.     vector < base > fa ( a. begin ( ) , a. end ( ) ) ,  fb ( b. begin ( ) , b. end ( ) ) ;
  37.     size_t n = 1 ;
  38.     while ( n < max ( a. size ( ) , b. size ( ) ) )  n <<= 1 ;
  39.     n <<= 1 ;
  40.     fa. resize ( n ) ,  fb. resize ( n ) ;
  41.  
  42.     fft ( fa, false ) ,  fft ( fb, false ) ;
  43.     for ( size_t i = 0 ; i < n ; ++ i )
  44.         fa [ i ] *= fb [ i ] ;
  45.     fft ( fa, true ) ;
  46.  
  47.     res. resize ( n ) ;
  48.     for ( size_t i = 0 ; i < n ; ++ i )
  49.         res [ i ] = (ll)( fa [ i ] . real ( ) + 0.5 ) ;
  50.     //while(res.size()>1&&res.back()==0)res.pop_back();
  51. // if number
  52.     /*  int carry = 0 ;
  53.     for ( size_t i = 0 ; i < n ; ++ i ) {
  54.         res [ i ] += carry ;
  55.         carry = res [ i ] / 10 ;
  56.         res [ i ] %= 10 ;
  57.     }*/
  58. }
  59. int main(){
  60.    // booster();
  61.    // read("input.txt");
  62.     string s;
  63.     cin>>s;
  64.     int len = s.length();
  65.     vl a,b,res1,res2,res3;
  66.     a.resize(len,0);
  67.     b.resize(len,0);
  68.     for(int i = 0;i<len;i++){
  69.         if(s[i]=='a')a[i] = 1;
  70.         else a[i] = 0;
  71.         b[len - i - 1] = a[i];
  72.     }
  73.  
  74.     multiply(a,b,res1);
  75.    
  76.     for(int i = 0;i<len;i++){
  77.         if(s[i]=='b')a[i] = 1;
  78.         else a[i] = 0;
  79.         b[len - i - 1] = a[i];
  80.  
  81.     }
  82.     multiply(a,b,res2);
  83.    
  84.     for(int i = 0;i<len;i++){
  85.         if(s[i]=='c')a[i] = 1;
  86.         else a[i] = 0;
  87.         b[len - i - 1] = a[i];
  88.     }
  89.     multiply(a,b,res3);
  90.     ll ans = 0;
  91.     int lenn = res1.size();
  92.     for(int i = len;i<lenn;i++){
  93.         ans = max(ans,res1[i] + res2[i] + res3[i]);
  94.     }
  95.     cout<<ans<<endl;
  96.     for(int i = len;i<lenn;i++){
  97.         if(res1[i] + res2[i] + res3[i]==ans)
  98.         cout<<i - len + 1<<" ";
  99.        
  100.     }
  101.  
  102.  
  103.  
  104.     return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement