Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // sometimes u need to use long double .so be careful
- typedef complex < double > base ;
- const double PI = 2*acos( 0.0 );
- void fft ( vector < base > & a, bool invert ) {
- int n = ( int ) a. size ( ) ;
- for ( int i = 1 , j = 0 ; i < n ; ++ i ) {
- int bit = n >> 1 ;
- for ( ; j >= bit ; bit >>= 1 )
- j -= bit ;
- j += bit ;
- if ( i < j )
- swap ( a [ i ] , a [ j ] ) ;
- }
- for ( int len = 2 ; len <= n ; len <<= 1 ) {
- double ang = 2 * PI / len * ( invert ? - 1 : 1 ) ;
- base wlen ( cos ( ang ) , sin ( ang ) ) ;
- for ( int i = 0 ; i < n ; i += len ) {
- base w ( 1 ) ;
- for ( int j = 0 ; j < len / 2 ; ++ j ) {
- base u = a [ i + j ] , v = a [ i + j + len / 2 ] * w ;
- a [ i + j ] = u + v ;
- a [ i + j + len / 2 ] = u - v ;
- w *= wlen ;
- }
- }
- }
- if ( invert )
- for ( int i = 0 ; i < n ; ++ i )
- a [ i ] /= n ;
- }
- void multiply ( const vector < ll > & a, const vector < ll > & b, vector < ll > & res ) {
- vector < base > fa ( a. begin ( ) , a. end ( ) ) , fb ( b. begin ( ) , b. end ( ) ) ;
- size_t n = 1 ;
- while ( n < max ( a. size ( ) , b. size ( ) ) ) n <<= 1 ;
- n <<= 1 ;
- fa. resize ( n ) , fb. resize ( n ) ;
- fft ( fa, false ) , fft ( fb, false ) ;
- for ( size_t i = 0 ; i < n ; ++ i )
- fa [ i ] *= fb [ i ] ;
- fft ( fa, true ) ;
- res. resize ( n ) ;
- for ( size_t i = 0 ; i < n ; ++ i )
- res [ i ] = (ll)( fa [ i ] . real ( ) + 0.5 ) ;
- //while(res.size()>1&&res.back()==0)res.pop_back();
- // if number
- /* int carry = 0 ;
- for ( size_t i = 0 ; i < n ; ++ i ) {
- res [ i ] += carry ;
- carry = res [ i ] / 10 ;
- res [ i ] %= 10 ;
- }*/
- }
- int main(){
- // booster();
- // read("input.txt");
- string s;
- cin>>s;
- int len = s.length();
- vl a,b,res1,res2,res3;
- a.resize(len,0);
- b.resize(len,0);
- for(int i = 0;i<len;i++){
- if(s[i]=='a')a[i] = 1;
- else a[i] = 0;
- b[len - i - 1] = a[i];
- }
- multiply(a,b,res1);
- for(int i = 0;i<len;i++){
- if(s[i]=='b')a[i] = 1;
- else a[i] = 0;
- b[len - i - 1] = a[i];
- }
- multiply(a,b,res2);
- for(int i = 0;i<len;i++){
- if(s[i]=='c')a[i] = 1;
- else a[i] = 0;
- b[len - i - 1] = a[i];
- }
- multiply(a,b,res3);
- ll ans = 0;
- int lenn = res1.size();
- for(int i = len;i<lenn;i++){
- ans = max(ans,res1[i] + res2[i] + res3[i]);
- }
- cout<<ans<<endl;
- for(int i = len;i<lenn;i++){
- if(res1[i] + res2[i] + res3[i]==ans)
- cout<<i - len + 1<<" ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement