算法题（最长回文子串的长度） _数据结构

本文概述

C ++
Java
Python3
C#
C ++
Java
C#
Python3
Python3

给定一个字符串小号长度?, 任务是找到最长回文子串从给定的字符串。
例子：

输入：S ="abcbab"
输出：5
说明：字符串" abcba"是最长的子字符串, 是回文, 长度为5。
输入：S ="abcdaa"
输出：2
说明：字符串" aa"是最长的子字符串那是回文长度为2的回文。

简单的方法：解决问题的最简单方法是生成给定字符串的所有可能的子字符串并打印长度最长子串这是一个回文.
下面是上述方法的实现：
C ++

//C++ program for the above approach #include < bits/stdc++.h> using namespace std; //Function to obtain the length of //the longest palindromic substring int longestPalSubstr(string str) { //Length of given string int n = str.size(); //Stores the maximum length int maxLength = 1, start = 0; //Iterate over the string for ( int i = 0; i < str.length(); i++) { //Iterate over the string for ( int j = i; j < str.length(); j++) { int flag = 1; //Check for palindrome for ( int k = 0; k < (j - i + 1) /2; k++) if (str[i + k] != str[j - k]) flag = 0; //If string [i, j - i + 1] //is palindromic if (flag & & (j - i + 1)> maxLength) { start = i; maxLength = j - i + 1; } } } //Return length of LPS return maxLength; } //Driver Code int main() { //Given string string str = "forgeeksskeegfor" ; //Function Call cout < < longestPalSubstr(str); return 0; }

Java

//Java program for the above approach import java.io.*; class GFG{//Function to obtain the length of //the longest palindromic substring static int longestPalSubstr(String str) {//Length of given string int n = str.length(); //Stores the maximum length int maxLength = 1 , start = 0 ; //Iterate over the string for ( int i = 0 ; i < str.length(); i++) {//Iterate over the string for ( int j = i; j < str.length(); j++) { int flag = 1 ; //Check for palindrome for ( int k = 0 ; k < (j - i + 1 ) /2 ; k++) if (str.charAt(i + k) != str.charAt(j - k)) flag = 0 ; //If string [i, j - i + 1] //is palindromic if (flag != 0 & & (j - i + 1 )> maxLength) { start = i; maxLength = j - i + 1 ; } } }//Return length of LPS return maxLength; }//Driver Code public static void main (String[] args) {//Given string String str = "forgeeksskeegfor" ; //Function call System.out.print(longestPalSubstr(str)); } } //This code is contributed by code_hunt

Python3

# Python3 program for the above approach # Function to obtain the length of # the longest palindromic substring def longestPalSubstr( str ):# Length of given string n = len ( str )# Stores the maximum length maxLength = 1 start = 0# Iterate over the string for i in range ( len ( str )):# Iterate over the string for j in range (i, len ( str ), 1 ): flag = 1# Check for palindrome for k in range ((j - i + 1 ) //2 ): if ( str [i + k] ! = str [j - k]): flag = 0# If string [i, j - i + 1] # is palindromic if (flag ! = 0 and (j - i + 1 )> maxLength): start = i maxLength = j - i + 1# Return length of LPS return maxLength # Driver Code # Given string str = "forgeeksskeegfor"# Function call print (longestPalSubstr( str )) # This code is contributed by code_hunt

//C# program for the above approach using System; class GFG{//Function to obtain the length of //the longest palindromic substring static int longestPalSubstr( string str) {//Length of given string int n = str.Length; //Stores the maximum length int maxLength = 1, start = 0; //Iterate over the string for ( int i = 0; i < str.Length; i++) {//Iterate over the string for ( int j = i; j < str.Length; j++) { int flag = 1; //Check for palindrome for ( int k = 0; k < (j - i + 1) /2; k++) if (str[i + k] != str[j - k]) flag = 0; //If string [i, j - i + 1] //is palindromic if (flag != 0 & & (j - i + 1)> maxLength) { start = i; maxLength = j - i + 1; } } }//Return length of LPS return maxLength; }//Driver Code public static void Main () {//Given string string str = "forgeeksskeegfor" ; //Function call Console.Write(longestPalSubstr(str)); } } //This code is contributed by code_hunt

输出如下：

10

时间复杂度：O(N^3), 其中N是给定字符串的长度。
辅助空间：O(N)
动态规划方法：通过存储以下结果可以优化上述方法重叠子问题。这个想法类似于这个帖子。步骤如下：

维护一个布尔表table[N][N]，以自底向上的方式填充。
如果子字符串是回文，表table[i][j]的值为true，否则为false。
计算表table[i][j]，检查表table[i + 1][j - 1]的值，如果值为true且str[i]与str[j]相同，则更新表table[i][j]的值为true。
否则, 表table[i] [j]的值被更新为false。

下面是字符串的插图"geeks":

文章图片
下面是上述方法的实现：
C ++

//C++ program for the above approach #include < bits/stdc++.h> using namespace std; //Function to find the length of //the longest palindromic substring int longestPalSubstr(string str) { //Length of string str int n = str.size(); //Stores the dp states bool table[n][n]; //Initialise table[][] as false memset (table, 0, sizeof (table)); //All substrings of length 1 //are palindromes int maxLength = 1; for ( int i = 0; i < n; ++i) table[i][i] = true ; //Check for sub-string of length 2 int start = 0; for ( int i = 0; i < n - 1; ++i) { //If adjacent character are same if (str[i] == str[i + 1]) { //Update table[i][i + 1] table[i][i + 1] = true ; start = i; maxLength = 2; } } //Check for lengths greater than 2 //k is length of substring for ( int k = 3; k < = n; ++k) { //Fix the starting index for ( int i = 0; i < n - k + 1; ++i) { //Ending index of substring //of length k int j = i + k - 1; //Check for palindromic //substring str[i, j] if (table[i + 1][j - 1] & & str[i] == str[j]) { //Mark true table[i][j] = true ; //Update the maximum length if (k> maxLength) { start = i; maxLength = k; } } } } //Return length of LPS return maxLength; } //Driver Code int main() { //Given string str string str = "forgeeksskeegfor" ; //Function Call cout < < longestPalSubstr(str); return 0; }

Java

//Java program for the above approach import java.util.*; class GFG{ //Function to find the length of //the longest palindromic subString static int longestPalSubstr(String str) {//Length of String str int n = str.length(); //Stores the dp states boolean [][]table = new boolean [n][n]; //All subStrings of length 1 //are palindromes int maxLength = 1 ; for ( int i = 0 ; i < n; ++i) table[i][i] = true ; //Check for sub-String of length 2 int start = 0 ; for ( int i = 0 ; i < n - 1 ; ++i) {//If adjacent character are same if (str.charAt(i) == str.charAt(i + 1 )) {//Update table[i][i + 1] table[i][i + 1 ] = true ; start = i; maxLength = 2 ; } } //Check for lengths greater than 2 //k is length of subString for ( int k = 3 ; k < = n; ++k) {//Fix the starting index for ( int i = 0 ; i < n - k + 1 ; ++i) {//Ending index of subString //of length k int j = i + k - 1 ; //Check for palindromic //subString str[i, j] if (table[i + 1 ][j - 1 ] & & str.charAt(i) == str.charAt(j)) {//Mark true table[i][j] = true ; //Update the maximum length if (k> maxLength) { start = i; maxLength = k; } } } }//Return length of LPS return maxLength; } //Driver Code public static void main(String[] args) {//Given String str String str = "forgeeksskeegfor" ; //Function Call System.out.print(longestPalSubstr(str)); } } //This code is contributed by Amit Katiyar

//C# program for //the above approach using System; class GFG{ //Function to find the length of //the longest palindromic subString static int longestPalSubstr(String str) { //Length of String str int n = str.Length; //Stores the dp states bool [, ]table = new bool [n, n]; //All subStrings of length 1 //are palindromes int maxLength = 1; for ( int i = 0; i < n; ++i) table[i, i] = true ; //Check for sub-String //of length 2 int start = 0; for ( int i = 0; i < n - 1; ++i) { //If adjacent character are same if (str[i] == str[i + 1]) { //Update table[i, i + 1] table[i, i + 1] = true ; start = i; maxLength = 2; } } //Check for lengths greater than 2 //k is length of subString for ( int k = 3; k < = n; ++k) { //Fix the starting index for ( int i = 0; i < n - k + 1; ++i) { //Ending index of subString //of length k int j = i + k - 1; //Check for palindromic //subString str[i, j] if (table[i + 1, j - 1] & & str[i] == str[j]) { //Mark true table[i, j] = true ; //Update the maximum length if (k> maxLength) { start = i; maxLength = k; } } } } //Return length of LPS return maxLength; } //Driver Code public static void Main(String[] args) { //Given String str String str = "forgeeksskeegfor" ; //Function Call Console.Write(longestPalSubstr(str)); } } //This code is contributed by Rajput-Ji

Python3

# Python program for the above approach # Function to find the length of # the longest palindromic subString def longestPalSubstr( str ): # Length of String str n = len ( str ); # Stores the dp states table = [[ False for i in range (n)] for j in range (n)]; # All subStrings of length 1 # are palindromes maxLength = 1 ; for i in range (n): table[i][i] = True ; # Check for sub-String of length 2 start = 0 ; for i in range (n - 1 ): # If adjacent character are same if ( str [i] = = str [i + 1 ]): # Update table[i][i + 1] table[i][i + 1 ] = True ; start = i; maxLength = 2 ; # Check for lengths greater than 2 # k is length of subString for k in range ( 3 , n + 1 ): # Fix the starting index for i in range (n - k + 1 ): # Ending index of subString # of length k j = i + k - 1 ; # Check for palindromic # subString str[i, j] if (table[i + 1 ][j - 1 ] and str [i] = = str [j]): # Mark True table[i][j] = True ; # Update the maximum length if (k> maxLength): start = i; maxLength = k; # Return length of LPS return maxLength; # Driver Code if __name__ = = '__main__' : # Given String str str = "forgeeksskeegfor" ; # Function Call print (longestPalSubstr( str )); # This code is contributed by 29AjayKumar

输出如下：

10

时间复杂度：O(N^2), 其中N是给定字符串的长度。
辅助空间：O(N))
高效方法：为了优化上述方法, 想法是使用经理的算法。通过使用此算法, 对于每个字符C, 最长的回文子串具有C因为它的中心长度是奇数。但是最长的回文子串也可以具有均匀的长度, 没有任何中心。因此, 可以在每个字符之间添加一些特殊字符。

例如, 如果给定的字符串是" abababc", 则它将变为" $＃a＃b＃a＃b＃a＃b＃c＃@"。现在, 请注意, 在这种情况下, 对于每个字符c, 以c为中心的最长回文子字符串的长度将为奇数。

步骤如下：

在给定的字符串中添加特殊字符小号如上所述, 让它的长度为?.
初始化数组d [], 中心和[R与0其中d [i]存储回文的左侧部分的长度, 其中S [i]是中心[R表示最右边的访问边界, 而center表示当前字符索引, 它是此最右边边界的中心。
在遍历字符串时小号, 对于每个索引一世如果我小于r那么它的答案就已经被计算过了d [i]可以设置为等于回答字符镜像一世中心可以计算为(2 *中心– i).
现在, 检查r后面是否有某些字符, 以使回文变得越来越长。
If(i + d [i])大于r, 更新r =(i + d [i])并以一世.
在找到每个角色最长的回文之后C作为中心, 打印最大值(2 * d [i] +1)/ 2其中0≤i < N因为d [i]仅存储回文的左侧部分。

下面是上述方法的实现：
Python3

# Python program for the above approach # Function that placed '#' intermediately # before and after each character def UpdatedString(string): newString = [ '#' ] # Traverse the string for char in string: newString + = [char, '#' ] # Return the string return ''.join(newString) # Function that finds the length of # the longest palindromic substring def Manacher(string): # Update the string string = UpdatedString(string) # Stores the longest proper prefix # which is also a suffix LPS = [ 0 for _ in range ( len (string))] C = 0 R = 0 for i in range ( len (string)): imir = 2 * C - i # Find the minimum length of # the palindrome if R> i: LPS[i] = min (R - i, LPS[imir]) else : # Find the actual length of # the palindrome LPS[i] = 0 # Exception Handling try : while string[i + 1 + LPS[i]] \ = = string[i - 1 - LPS[i]]: LPS[i] + = 1 except : pass # Update C and R if i + LPS[i]> R: C = i R = i + LPS[i] r, c = max (LPS), LPS.index( max (LPS)) # Return the length r return r # Driver code # Given string str str = "forgeeksskeegfor" # Function Call print (Manacher( str ))

输出如下：