Queries to check if string B exists as substring in string A | Java implementation of the approach ; Function to return the modular inverse using Fermat 's little theorem ; Function to generate hash ; To store prefix - sum of rolling hash ; Multiplier for different values of i ; Generating hash value for string b ; Generating prefix - sum of hash of a ; Function that returns true if the required sub - string in a is equal to b ; To store hash of required sub - string of A ; If i = 0 then requires hash value ; Required hash if i != 0 ; Comparing hash with hash of B ; Driver code ; Generating hash ; Queries ; Perform queries
import java . util . * ; class GFG { static int mod = 3803 ; static int d = 26 ; static int hash_b ; static int [ ] hash_a ; static int [ ] mul ; static int mi ( int x ) { int p = mod - 2 ; int s = 1 ; while ( p != 1 ) { if ( p % 2 == 1 ) { s = ( s * x ) % mod ; } x = ( x * x ) % mod ; p /= 2 ; } return ( s * x ) % mod ; } static void genHash ( char [ ] a , char [ ] b ) { hash_a = new int [ a . length ] ; mul = new int [ a . length ] ; for ( int i = b . length - 1 ; i >= 0 ; i -- ) { hash_b = ( hash_b * d + ( b [ i ] - 97 ) ) % mod ; } mul [ 0 ] = 1 ; hash_a [ 0 ] = ( a [ 0 ] - 97 ) % mod ; for ( int i = 1 ; i < a . length ; i ++ ) { mul [ i ] = ( mul [ i - 1 ] * d ) % mod ; hash_a [ i ] = ( hash_a [ i - 1 ] + mul [ i ] * ( a [ i ] - 97 ) ) % mod ; } } static boolean checkEqual ( int i , int len_a , int len_b ) { int x ; if ( i == 0 ) { x = hash_a [ len_b - 1 ] ; } else { x = ( hash_a [ i + len_b - 1 ] - hash_a [ i - 1 ] + 2 * mod ) % mod ; x = ( x * mi ( mul [ i ] ) ) % mod ; } if ( x == hash_b ) { return true ; } return false ; } public static void main ( String [ ] args ) { String a = " abababababa " ; String b = " aba " ; genHash ( a . toCharArray ( ) , b . toCharArray ( ) ) ; int queries [ ] = { 0 , 1 , 2 , 3 } ; int q = queries . length ; for ( int i = 0 ; i < q ; i ++ ) { if ( checkEqual ( queries [ i ] , a . length ( ) , b . length ( ) ) ) { System . out . println ( " Yes " ) ; } else { System . out . println ( " No " ) ; } } } }