Queries to check if substring [ L ... R ] is palindrome or not | PHP implementation of the approach ; Pre - processing function ; Get the size of the string ; Initially mark every position as false ; For the length ; Iterate for every index with length j ; If the length is less than 2 ; If characters are equal ; Check for equal ; Function to answer every query in O ( 1 ) ; Driver code
< ? php $ N = 100 ; function pre_process ( $ dp , $ s ) { $ n = strlen ( $ s ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { for ( $ j = 0 ; $ j < $ n ; $ j ++ ) $ dp [ $ i ] [ $ j ] = false ; } for ( $ j = 1 ; $ j <= $ n ; $ j ++ ) { for ( $ i = 0 ; $ i <= $ n - $ j ; $ i ++ ) { if ( $ j <= 2 ) { if ( $ s [ $ i ] == $ s [ $ i + $ j - 1 ] ) $ dp [ $ i ] [ $ i + $ j - 1 ] = true ; } else if ( $ s [ $ i ] == $ s [ $ i + $ j - 1 ] ) $ dp [ $ i ] [ $ i + $ j - 1 ] = $ dp [ $ i + 1 ] [ $ i + $ j - 2 ] ; } } return $ dp ; } function answerQuery ( $ l , $ r , $ dp ) { if ( $ dp [ $ l ] [ $ r ] ) echo " Yes STRNEWLINE " ; else echo " No STRNEWLINE " ; } $ s = " abaaab " ; $ dp = array ( array ( ) ) ; $ dp = pre_process ( $ dp , $ s ) ; $ queries = array ( array ( 0 , 1 ) , array ( 1 , 5 ) ) ; $ q = count ( $ queries ) ; for ( $ i = 0 ; $ i < $ q ; $ i ++ ) answerQuery ( $ queries [ $ i ] [ 0 ] , $ queries [ $ i ] [ 1 ] , $ dp ) ; ? >