가장 긴 회문 부분 문자열

주어진 문자열에서 가장 긴 회문인 부분 문자열을 찾아야 합니다.

가장 긴 회문 하위 문자열을 얻으려면 많은 하위 문제를 해결해야 하며 일부 하위 문제는 겹칩니다. 그들은 여러 번 해결해야합니다. 그런 이유로 동적 프로그래밍이 도움이 됩니다. 테이블을 사용하여 이전 하위 문제의 결과를 저장할 수 있으며 단순히 추가 결과를 생성하는 데 사용할 수 있습니다.

입력 및 출력

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