fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std ;
  3. string a , b , ra , rb ;
  4. int l ;
  5. int zab[2000000+5] , zarb[2000000+5] , zrab[2000000+5] ;
  6. int llll = 0 ;
  7. void Zcalc(string s , int *z) {
  8.   memset( z , 0 , sizeof z ) ;
  9.   int L = 0, R = 0;
  10.   int n = s.size() ;
  11.   for (int i = 1; i < n ; i++) {
  12.     if (i > R) {
  13.       L = R = i;
  14.       while (R < n && s[R-L] == s[R]) R++;
  15.       z[i] = R-L;
  16.       R--;
  17.     } else {
  18.       int k = i-L;
  19.       if (z[k] < R-i+1) z[i] = z[k];
  20.       else {
  21.         L = i;
  22.         while (R < n && s[R-L] == s[R]) R++;
  23.         z[i] = R-L;
  24.         R--;
  25.       }
  26.     }
  27.   }
  28. }
  29.  
  30. int main() {
  31.  
  32.   while( getline(cin , a ) ) {
  33.  
  34.     getline(cin , b ) ;
  35.     if( (a.size() == 1 && b.size() ==1)||(a.size() != b.size()) ){
  36.       cout << -1 << " " << -1 << endl ;
  37.       continue ;
  38.     }
  39.     ra = a ;
  40.     reverse(ra.begin(),ra.end()) ;
  41.     rb = b ;
  42.     reverse(rb.begin(),rb.end()) ;
  43.  
  44.     l= a.size()+b.size()+1 ;
  45.  
  46.     Zcalc(b+'\x7F'+a,zab);
  47.     Zcalc(a+'\x7F'+rb,zarb);
  48.     Zcalc(ra+'\x7F'+b,zrab);
  49.  
  50.     int ansI=-1 , ansJ=10000000 ;
  51.  
  52.     for( int i = b.size()+1, j = 0  ; i < l ; i++ , j++ ) {
  53.       int I = j ;
  54.       int J = j+zab[i] ;
  55.       int leftLen = j ;
  56.       int checkLeftLen = zarb[a.size()+1] ;
  57.       if( checkLeftLen >= leftLen ) {
  58.         int rightLen = a.size()+b.size()-i-zab[i]+1 ;
  59.         int checkRightLen = zrab[ a.size() + 1 + zab[i] ];
  60.         if( checkRightLen >= rightLen ){
  61.           if( I > ansI )ansI = I , ansJ = J ;
  62.           else if( I == ansI ){
  63.             if( J < ansJ ){
  64.               ansJ = J ;
  65.             }
  66.           }
  67.         }
  68.       }
  69.     }
  70.     if( ansI+1 == ansJ ) ansJ-- ;
  71.     if( ansI == -1 )cout << -1 << " " << -1 << "\n" ;
  72.     else cout << ansI-1 << " " << ansJ << "\n" ;
  73.  
  74.   }
  75.   return 0 ;
  76. }
  77.  
  78.  
  79.  
Success #stdin #stdout 0s 26584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2Cz6rV
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!