La substring palindrómica más larga usando el árbol palindrómico | conjunto 3

Dada una string, encuentra la substring más larga que es palíndromo. Por ejemplo, si la string dada es «forgeeksskeegfor», la salida debería ser «geeksskeeg».

Prerrequisito: Árbol palindrómico | Substring palindrómica más larga

Estructura del árbol
palindrómico: la estructura real del árbol palindrómico está cerca del gráfico dirigido. En realidad, es una estructura fusionada de dos árboles que comparten algunos Nodes comunes (consulte la figura a continuación para una mejor comprensión). Los Nodes de árbol almacenan substrings palindrómicas de una string dada al almacenar sus índices.
Este árbol consta de dos tipos de aristas:
1. Arista de inserción (arista ponderada)
2. Sufijo palindrómico máximo (no ponderado)

Borde de inserción:
el borde de inserción de un Node u a v con algo de peso x significa que el Node v se forma insertando x al frente y al final de la string en u. Como ‘u’ ya es un palíndromo, la string resultante en el Node v también será un palíndromo. x será un solo carácter para cada borde. Por lo tanto, un Node puede tener un máximo de 26 bordes de inserción (considerando la string de letras más bajas).
Borde máximo del sufijo palindrómico:
Como el propio nombre indica que para un Node, este borde apuntará a su Node String de sufijo palindrómico máximo. No consideraremos la string completa en sí misma como el sufijo palindrómico máximo, ya que esto no tendrá sentido (bucles propios). Por motivos de simplicidad, lo llamaremos borde de sufijo (con lo que nos referimos al sufijo máximo excepto la string completa). Es bastante obvio que cada Node tendrá solo 1 borde de sufijo, ya que no almacenaremos strings duplicadas en el árbol.
Crearemos todas las substrings palindrómicas y luego devolveremos la última que obtuvimos, ya que esa sería la substring palindrómica más larga hasta el momento.
Dado que un árbol palindrómico almacena los palíndromos en orden de llegada de un determinado carácter, el más largo siempre estará en el último índice de nuestra array de árbol.
A continuación se muestra la implementación del enfoque anterior:

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

// JAVA code for Longest Palindromic subString 
// using Palindromic Tree data structure 
class GFG 
{
  
    static final int MAXN = 1000;
  
    static class Node
    {
        // store start and end indexes of current
        // Node inclusively
        int start, end;
  
        // stores length of subString
        int length;
  
        // stores insertion Node for all characters a-z
        int[] insertionEdge = new int[26];
  
        // stores the Maximum Palindromic Suffix Node for
        // the current Node
        int suffixEdge;
    };
  
    // two special dummy Nodes as explained above
    static Node root1, root2;
  
    // stores Node information for constant time access
    static Node[] tree = new Node[MAXN];
  
    // Keeps track the current Node while insertion
    static int currNode;
    static char[] s;
    static int ptr;
  
    // Function to insert edge in tree
    static void insert(int currIndex)
    {
        // Finding X, such that s[currIndex]
        // + X + s[currIndex] is palindrome.
        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;
        }
  
        // Check if s[currIndex] + X +
        // s[currIndex] is already Present in tree.
        if (tree[temp].insertionEdge[s[currIndex] - 'a'] != 0)
        {
            currNode = tree[temp].insertionEdge[s[currIndex] - 'a'];
  
            return;
        }
  
        // Else Create new node;
        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;
  
        // Setting suffix edge for newly Created Node.
  
        currNode = ptr;
        temp = tree[temp].suffixEdge;
  
        // Longest Palindromic suffix for a
        // String of length 1 is a Null String.
        if (tree[currNode].length == 1)
        {
            tree[currNode].suffixEdge = 2;
            return;
        }
  
        // Else
        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'];
    }
  
    // Driver code
    public static void main(String[] args) 
    {
        // Imaginary root's suffix edge points to
        // itself, since for an imaginary String
        // of length = -1 has an imaginary suffix
        // String. Imaginary root.
        root1 = new Node();
        root1.length = -1;
        root1.suffixEdge = 1;
  
        // null root's suffix edge points to
        // Imaginary root, since for a String
        // of length = 0 has an imaginary suffix String.
        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);
  
        // last will be the index of our last subString
        int last = ptr;
  
        for (int i = tree[last].start; i <= tree[last].end; i++)
            System.out.print(s[i]);
  
    }
}
  
// This code is contributed by Rajput-Ji

# Python3 code for Longest Palindromic 
# substring using Palindromic Tree 
# data structure 
  
class Node: 
      
    def __init__(self, length = None, 
                       suffixEdge = None):
          
        # store start and end indexes 
        # of current Node inclusively 
        self.start = None
        self.end = None
          
        # Stores length of substring 
        self.length = length 
  
        # stores insertion Node for all
        # characters a-z 
        self.insertionEdge = [0] * 26
  
        # stores the Maximum Palindromic 
        # Suffix Node for the current Node 
        self.suffixEdge = suffixEdge 
  
# Function to insert edge in tree 
def insert(currIndex): 
      
    global currNode, ptr
      
    # Finding X, such that s[currIndex] 
    # + X + s[currIndex] is palindrome. 
    temp = currNode 
  
    while True: 
      
        currLength = tree[temp].length 
        if (currIndex - currLength >= 1 and
           (s[currIndex] == s[currIndex -
            currLength - 1])): 
            break
  
        temp = tree[temp].suffixEdge 
  
    # Check if s[currIndex] + X + 
    # s[currIndex] is already Present in tree. 
    if tree[temp].insertionEdge[ord(s[currIndex]) - 
                                ord('a')] != 0: 
      
        currNode = tree[temp].insertionEdge[ord(s[currIndex]) - 
                                            ord('a')] 
        return
      
    # Else Create new node 
    ptr += 1
  
    tree[temp].insertionEdge[ord(s[currIndex]) - 
                             ord('a')] = ptr 
  
    tree[ptr].end = currIndex 
  
    tree[ptr].length = tree[temp].length + 2
  
    tree[ptr].start = (tree[ptr].end - 
                       tree[ptr].length + 1)
  
    # Setting suffix edge for newly Created Node. 
    currNode = ptr 
    temp = tree[temp].suffixEdge 
  
    # Longest Palindromic suffix for a 
    # string of length 1 is a Null string. 
    if tree[currNode].length == 1: 
        tree[currNode].suffixEdge = 2
        return
  
    # Else 
    while True: 
        currLength = tree[temp].length 
  
        if (currIndex - currLength >= 1 and
            s[currIndex] == s[currIndex - 
                              currLength - 1]): 
            break
  
        temp = tree[temp].suffixEdge 
  
    tree[currNode].suffixEdge = \
    tree[temp].insertionEdge[ord(s[currIndex]) - ord('a')] 
  
# Driver code 
if __name__ == "__main__":
      
    MAXN = 1000
      
    # Imaginary root's suffix edge points to 
    # itself, since for an imaginary string 
    # of length = -1 has an imaginary suffix 
    # string. Imaginary root.
    root1 = Node(-1, 1) 
  
    # NULL root's suffix edge points to 
    # Imaginary root, since for a string of 
    # length = 0 has an imaginary suffix string. 
    root2 = Node(0, 1)
      
    # Stores Node information for 
    # constant time access 
    tree = [Node() for i in range(MAXN)] 
      
    # Keeps track the Current Node 
    # while insertion 
    currNode, ptr = 1, 2
      
    tree[1] = root1 
    tree[2] = root2 
  
    s = "forgeeksskeegfor"
    for i in range(0, len(s)): 
        insert(i) 
  
    # last will be the index of our
    # last substring 
    last = ptr 
    for i in range(tree[last].start,
                   tree[last].end + 1): 
        print(s[i], end = "") 
  
# This code is contributed by Rituraj Jain

// C# code for longest Palindromic subString 
// using Palindromic Tree data structure 
using System;
  
class GFG 
{
  
    static readonly int MAXN = 1000;
  
    class Node
    {
        // store start and end indexes of current
        // Node inclusively
        public int start, end;
  
        // stores length of subString
        public int Length;
  
        // stores insertion Node for all characters a-z
        public int[] insertionEdge = new int[26];
  
        // stores the Maximum Palindromic Suffix Node for
        // the current Node
        public int suffixEdge;
    };
  
    // two special dummy Nodes as explained above
    static Node root1, root2;
  
    // stores Node information for constant time access
    static Node[] tree = new Node[MAXN];
  
    // Keeps track the current Node while insertion
    static int currNode;
    static char[] s;
    static int ptr;
  
    // Function to insert edge in tree
    static void insert(int currIndex)
    {
        // Finding X, such that s[currIndex]
        // + X + s[currIndex] is palindrome.
        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;
        }
  
        // Check if s[currIndex] + X +
        // s[currIndex] is already Present in tree.
        if (tree[temp].insertionEdge[s[currIndex] - 'a'] != 0)
        {
            currNode = tree[temp].insertionEdge[s[currIndex] - 'a'];
  
            return;
        }
  
        // Else Create new node;
        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;
  
        // Setting suffix edge for newly Created Node.
        currNode = ptr;
        temp = tree[temp].suffixEdge;
  
        // longest Palindromic suffix for a
        // String of length 1 is a Null String.
        if (tree[currNode].Length == 1)
        {
            tree[currNode].suffixEdge = 2;
            return;
        }
  
        // Else
        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'];
    }
  
    // Driver code
    public static void Main(String[] args) 
    {
        // Imaginary root's suffix edge points to
        // itself, since for an imaginary String
        // of length = -1 has an imaginary suffix
        // String. Imaginary root.
        root1 = new Node();
        root1.Length = -1;
        root1.suffixEdge = 1;
  
        // null root's suffix edge points to
        // Imaginary root, since for a String
        // of length = 0 has an imaginary suffix String.
        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);
  
        // last will be the index of our last subString
        int last = ptr;
  
        for (int i = tree[last].start; i <= tree[last].end; i++)
            Console.Write(s[i]);
  
    }
}
  
// This code is contributed by Rajput-Ji

geeksskeeg