Queries to check if substring [ L ... R ] is palindrome or not | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100 NEW_LINE void pre_process ( bool dp [ N ] [ N ] , string s ) { int n = s . size ( ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) dp [ i ] [ j ] = false ; } for ( int j = 1 ; j <= n ; j ++ ) { for ( int 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 ] ; } } } void answerQuery ( int l , int r , bool dp [ N ] [ N ] ) { if ( dp [ l ] [ r ] ) cout << " Yes STRNEWLINE " ; else cout << " No STRNEWLINE " ; } int main ( ) { string s = " abaaab " ; bool dp [ N ] [ N ] ; pre_process ( dp , s ) ; int queries [ ] [ 2 ] = { { 0 , 1 } , { 1 , 5 } } ; int q = sizeof ( queries ) / sizeof ( queries [ 0 ] ) ; for ( int i = 0 ; i < q ; i ++ ) answerQuery ( queries [ i ] [ 0 ] , queries [ i ] [ 1 ] , dp ) ; return 0 ; }