最长回文子串
在给定的字符串中，我们必须找到一个子字符串，它是回文，并且最长。
要获得最长的回文子串，我们必须解决许多子问题，其中一些子问题是重叠的。它们需要多次解决。因此，动态编程很有用。使用表，我们可以存储先前子问题的结果，并简单地使用它们来生成进一步的结果。
输入输出
Input: A String. Say “thisispalapsiti” Output: The palindrome substring and the length of the palindrome. Longest palindrome substring is: ispalapsi Length is: 9
算法
findLongPalSubstr(str)
输入-主字符串。
输出-最长回文子串及其长度。
Begin
n := length of the given string
create a n x n table named palTab to store true or false value
fill patTab with false values
maxLen := 1
for i := 0 to n-1, do
patTab[i, i] = true //as it is palindrome of length 1
done
start := 0
for i := 0 to n-2, do
if str[i] = str[i-1], then
palTab[i, i+1] := true
start := i
maxLen := 2
done
for k := 3 to n, do
for i := 0 to n-k, do
j := i + k – 1
if palTab[i+1, j-1] and str[i] = str[j], then
palTab[i, j] := true
if k > maxLen, then
start := i
maxLen := k
done
done
display substring from start to maxLen from str, and return maxLen
End示例
#include<iostream>
using namespace std;
int findLongPalSubstr(string str) {
int n = str.size(); // get length of input string
bool palCheckTab[n][n]; //true when substring from i to j is palindrome
for(int i = 0; i<n; i++)
for(int j = 0; j<n; j++)
palCheckTab[i][j] = false; //initially set all values to false
int maxLength = 1;
for (int i = 0; i < n; ++i)
palCheckTab[i][i] = true; //as all substring of length 1 is palindrome
int start = 0;
for (int i = 0; i < n-1; ++i) {
if (str[i] == str[i+1]) { //for two character substring both characters are equal
palCheckTab[i][i+1] = true;
start = i;
maxLength = 2;
}
}
for (int k = 3; k <= n; ++k) { //for substrings with length 3 to n
for (int i = 0; i < n-k+1 ; ++i) {
int j = i + k - 1;
if (palCheckTab[i+1][j-1] && str[i] == str[j]) { //if (i,j) and (i+1, j-1) are same, then check palindrome
palCheckTab[i][j] = true;
if (k > maxLength) {
start = i;
maxLength = k;
}
}
}
}
cout << "Longest palindrome substring is: " << str.substr(start, maxLength) << endl;
return maxLength; // return length
}
int main() {
char str[] = "thisispalapsiti";
cout << "Length is: "<< findLongPalSubstr(str);
}输出结果
Longest palindrome substring is: ispalapsi Length is: 9