A Function to calculate the prefix hash
static void computePrefixHash ( String str , int n , int prefix [ ] , int power [ ] ) { prefix [ 0 ] = 0 ; prefix [ 1 ] = str . charAt ( 0 ) ; for ( int i = 2 ; i <= n ; i ++ ) { prefix [ i ] = ( prefix [ i - 1 ] % MOD + ( str . charAt ( i - 1 ) % MOD * power [ i - 1 ] % MOD ) % MOD ) % MOD ; } return ; }