# CFR 126 B. Password ( Hash + Binary Search )

Problem - 126B - Codeforces

```const int MSZ = 2; // MOD size ( number of attempts of verifying hash
const int MOD[] = { ( int ) 1e9 + 7, ( int ) 1e9 + 9 };
const int BASE[] = { ( int ) 1023, ( int ) 1e4 + 7 };

string seq;

void init(){
cin >> seq;
}

vvi pbase; // power base
vvi phash; // prefix hash

void preprocess(){
pbase = phash = vvi( MSZ, vi( seq.size() + 1 ) );
for( int i = 0; i < MSZ; ++i ){
pbase[ i ][ 0 ] = 1;
for( int j = 0; j < seq.size(); ++j ){
pbase[ i ][ j + 1 ] = 1LL * pbase[ i ][ j ] * BASE[ i ] % MOD[ i ],
phash[ i ][ j + 1 ] = ( 1LL * phash[ i ][ j ] * BASE[ i ] + seq[ j ] ) % MOD[ i ];
}
}
}

int get_hash( const vi &pbase, const vi &phash, int mod, int ql, int qr ){ // [ ql, qr )
int res = phash[ qr ] - 1LL * phash[ ql ] * pbase[ qr - ql ] % mod;
res %= mod, res += mod, res %= mod;
return res;
}

void solve(){
vi test;
for( int i = 1; i < seq.size(); ++i ){
int ok = 1;
for( int j = 0; j < MSZ; ++j )
if( get_hash( pbase[ j ], phash[ j ], MOD[ j ], 0, i ) != get_hash( pbase[ j ], phash[ j ], MOD[ j ], seq.size() - i, seq.size() ) )
ok = 0;
if( ok )
test.push_back( i );
}

int lb = 0, rb = test.size() - 1;
int ans = -1;
while( lb <= rb ){
int mid = lb + rb >> 1;
int x = test[ mid ];

int ok = 0;

for( int j = 1; j < seq.size() - x; ++j ){
int ng = 0;
for( int k = 0; k < MSZ; ++k )
if( get_hash( pbase[ k ], phash[ k ], MOD[ k ], 0, x ) != get_hash( pbase[ k ], phash[ k ], MOD[ k ], j, j + x ) )
ng = 1;
if( not ng )
ok = 1;
}

if( ok )
ans = mid, lb = mid + 1;
else
rb = mid - 1;
}
if( ans == -1 )
cout << "Just a legend" << endl;
else
cout << seq.substr( 0, test[ ans ] ) << endl;
}
```