Queries to check if string B exists as substring in string A | C ++ 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
#include <bits/stdc++.h> NEW_LINE #define mod  3803 NEW_LINE #define d  26 NEW_LINE using namespace std ; int hash_b ; int * hash_a ; int * mul ; 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 ; } void genHash ( string & a , string & b ) { hash_a = new int [ a . size ( ) ] ; mul = new int [ a . size ( ) ] ; for ( int i = b . size ( ) - 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 . size ( ) ; i ++ ) { mul [ i ] = ( mul [ i - 1 ] * d ) % mod ; hash_a [ i ] = ( hash_a [ i - 1 ] + mul [ i ] * ( a [ i ] - 97 ) ) % mod ; } } bool 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 ; } int main ( ) { string a = " abababababa " ; string b = " aba " ; genHash ( a , b ) ; int queries [ ] = { 0 , 1 , 2 , 3 } ; int q = sizeof ( queries ) / sizeof ( queries [ 0 ] ) ; for ( int i = 0 ; i < q ; i ++ ) { if ( checkEqual ( queries [ i ] , a . size ( ) , b . size ( ) ) ) cout << " Yes STRNEWLINE " ; else cout << " No STRNEWLINE " ; } return 0 ; }