最長の回文部分文字列

指定された文字列で、回文で最も長い部分文字列を見つける必要があります。

最長のパリンドローム部分文字列を取得するには、多くのサブ問題を解決する必要があります。いくつかのサブ問題は重複しています。それらは複数回解決する必要があります。そのため、動的計画法が役立ちます。テーブルを使用すると、前のサブ問題の結果を保存し、それらを使用してさらに結果を生成できます。

入力と出力

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