Chuỗi con Palindromic dài nhất

Trong một chuỗi nhất định, chúng ta phải tìm một chuỗi con, là một palindrome và nó dài nhất.

Để có được chuỗi con palindromic dài nhất, chúng ta phải giải nhiều bài toán con, một số bài toán con bị trùng lặp. Chúng cần được giải quyết nhiều lần. Vì lý do đó, lập trình Động rất hữu ích. Sử dụng bảng, chúng tôi có thể lưu trữ kết quả của các bài toán con trước đó và chỉ cần sử dụng chúng để tạo ra các kết quả khác.

Đầu vào và Đầu ra

Input:
A String. Say “thisispalapsiti”
Output:
The palindrome substring and the length of the palindrome.
Longest palindrome substring is: ispalapsi
Length is: 9

Thuật toán

findLongPalSubstr(str)

Đầu vào - Chuỗi chính.

Đầu ra - Chuỗi con palindromic dài nhất và độ dài của nó.

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

Ví dụ

#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);
}

Đầu ra

Longest palindrome substring is: ispalapsi
Length is: 9