Longest Palindromic Substring using Palindromic Tree | Set 3 | JAVA 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
class GFG { static final int MAXN = 1000 ; static class Node { int start , end ; int length ; int [ ] insertionEdge = new int [ 26 ] ; int suffixEdge ; } ; static Node root1 , root2 ; static Node [ ] tree = new Node [ MAXN ] ; static int currNode ; static char [ ] s ; static int ptr ; static 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 ' ] ; } public static void main ( String [ ] args ) { root1 = new Node ( ) ; root1 . length = - 1 ; root1 . suffixEdge = 1 ; root2 = new Node ( ) ; root2 . length = 0 ; root2 . suffixEdge = 1 ; for ( int i = 0 ; i < MAXN ; i ++ ) tree [ i ] = new Node ( ) ; tree [ 1 ] = root1 ; tree [ 2 ] = root2 ; ptr = 2 ; currNode = 1 ; s = " forgeeksskeegfor " . toCharArray ( ) ; for ( int i = 0 ; i < s . length ; i ++ ) insert ( i ) ; int last = ptr ; for ( int i = tree [ last ] . start ; i <= tree [ last ] . end ; i ++ ) System . out . print ( s [ i ] ) ; } }