# 算法题：最长回文子串的长度

2021年4月27日17:08:00 发表评论 761 次浏览

## 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#

``````//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``

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

## 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 (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 (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#

``````//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 (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``

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

``10``