最长回文子串

在给定的字符串中，我们必须找到一个子字符串，它是回文，并且最长。

要获得最长的回文子串，我们必须解决许多子问题，其中一些子问题是重叠的。它们需要多次解决。因此，动态编程很有用。使用表，我们可以存储先前子问题的结果，并简单地使用它们来生成进一步的结果。

输入输出

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