Самая длинная палиндромная подстрока с использованием палиндромного дерева | Комплект 3
Для данной строки найдите самую длинную подстроку, которая является палиндромом. Например, если задана строка «forgeeksskeegfor», вывод должен быть «geeksskeeg».
Предпосылка: Палиндромное дерево | Самая длинная палиндромная подстрока
Структура палиндромного дерева:
Фактическая структура палиндромного дерева близка к ориентированному графу. На самом деле это объединенная структура из двух Деревьев, которые имеют общие узлы (см. Рисунок ниже для лучшего понимания). Узлы дерева хранят палиндромные подстроки данной строки, сохраняя их индексы.
Это дерево состоит из двух типов ребер:
1. Вставная кромка (утяжеленная кромка)
2. Максимальный палиндромный суффикс (невзвешенный)
Insertion Edge :
Insertion edge from a node u to v with some weight x means that the node v is formed by inserting x at the front and end of the string at u. As ‘u’ is already a palindrome, hence the resulting string at node v will also be a palindrome. x will be a single character for every edge. Therefore, a node can have max 26 insertion edges (considering lower letter string).
Maximum Palindromic Suffix Edge :
As the name itself indicates that for a node this edge will point to its Maximum Palindromic Suffix String node. We will not be considering the complete string itself as the Maximum Palindromic Suffix as this will make no sense(self loops). For simplicity purpose, we will call it as Suffix edge(by which we mean maximum suffix except the complete string). It is quite obvious that every node will have only 1 Suffix Edge as we will not store duplicate strings in the tree.
We will create all the palindromic substrings and then return the last one we got, since that would be the longest palindromic substring so far.
Since a Palindromic Tree stores the palindromes in order of arrival of a certain character, so the Longest will always be at the last index of our tree array.
Below is the implementation of above approach :
C++
// 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
// 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
# 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
|