Longest Palindromic Substring using Palindromic Tree | Set 3 | CPP code for Longest Palindromic substring using Palindromic Tree data structure ; store start and end indexes of current Node inclusively ; stores length of substring ; stores insertion Node for all characters a - z ; stores the Maximum Palindromic Suffix Node for the current Node ; two special dummy Nodes as explained above ; stores Node information for constant time access ; Keeps track the current Node while insertion ; Function to insert edge in tree ; Finding X , such that s [ currIndex ] + X + s [ currIndex ] is palindrome . ; Check if s [ currIndex ] + X + s [ currIndex ] is already Present in tree . ; Else Create new node ; ; Setting suffix edge for newly Created Node . ; Longest Palindromic suffix for a string of length 1 is a Null string . ; Else ; Driver code ; Imaginary root 's suffix edge points to  itself, since for an imaginary string  of length = -1 has an imaginary suffix  string. Imaginary root. ; NULL root 's suffix edge points to  Imaginary root, since for a string  of length = 0 has an imaginary suffix string. ; last will be the index of our last substring
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAXN  1000 NEW_LINE struct Node { int start , end ; int length ; int insertionEdge [ 26 ] ; int suffixEdge ; } ; Node root1 , root2 ; Node tree [ MAXN ] ; int currNode ; string s ; int ptr ; void insert ( int currIndex ) { int temp = currNode ; while ( true ) { int currLength = tree [ temp ] . length ; if ( currIndex - currLength >= 1 && ( s [ currIndex ] == s [ currIndex - currLength - 1 ] ) ) break ; temp = tree [ temp ] . suffixEdge ; } if ( tree [ temp ] . insertionEdge [ s [ currIndex ] - ' a ' ] != 0 ) { currNode = tree [ temp ] . insertionEdge [ s [ currIndex ] - ' a ' ] ; return ; } ptr ++ ; tree [ temp ] . insertionEdge [ s [ currIndex ] - ' a ' ] = ptr ; tree [ ptr ] . end = currIndex ; tree [ ptr ] . length = tree [ temp ] . length + 2 ; tree [ ptr ] . start = tree [ ptr ] . end - tree [ ptr ] . length + 1 ; currNode = ptr ; temp = tree [ temp ] . suffixEdge ; if ( tree [ currNode ] . length == 1 ) { tree [ currNode ] . suffixEdge = 2 ; return ; } while ( true ) { int currLength = tree [ temp ] . length ; if ( currIndex - currLength >= 1 && ( s [ currIndex ] == s [ currIndex - currLength - 1 ] ) ) break ; temp = tree [ temp ] . suffixEdge ; } tree [ currNode ] . suffixEdge = tree [ temp ] . insertionEdge [ s [ currIndex ] - ' a ' ] ; } int main ( ) { root1 . length = -1 ; root1 . suffixEdge = 1 ; root2 . length = 0 ; root2 . suffixEdge = 1 ; tree [ 1 ] = root1 ; tree [ 2 ] = root2 ; ptr = 2 ; currNode = 1 ; s = " forgeeksskeegfor " ; for ( int i = 0 ; i < s . size ( ) ; i ++ ) insert ( i ) ; int last = ptr ; for ( int i = tree [ last ] . start ; i <= tree [ last ] . end ; i ++ ) cout << s [ i ] ; return 0 ; }