สตริงย่อยพาลินโดรมที่ยาวที่สุด

ในสตริงที่กำหนด เราต้องหาสตริงย่อย ซึ่งเป็นพาลินโดรมและยาวที่สุด

เพื่อให้ได้สตริงย่อยพาลินโดรมที่ยาวที่สุด เราต้องแก้ปัญหาย่อยหลายๆ อย่าง ปัญหาย่อยบางรายการซ้อนทับกัน จำเป็นต้องแก้ไขหลายครั้ง ด้วยเหตุผลดังกล่าว โปรแกรมไดนามิกจึงมีประโยชน์ เมื่อใช้ตาราง เราสามารถจัดเก็บผลลัพธ์ของปัญหาย่อยก่อนหน้า และใช้เพื่อสร้างผลลัพธ์เพิ่มเติมได้

อินพุตและเอาต์พุต

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