Trình tự Palindromic dài nhất trong C ++

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm độ dài của dãy con palindromic dài nhất tính bằng s. Chúng ta có thể giả định rằng độ dài tối đa của s là 1000. Vì vậy, nếu đầu vào giống như “bbbab”, thì đầu ra sẽ là 4. Một dãy con palindromic có thể có là “bbbb”.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• x:=s, sau đó đảo ngược x, n:=kích thước của s
• nếu n là 0, thì trả về 0
• cập nhật s bằng cách thêm một khoảng trống trước s và cập nhật x bằng cách thêm một khoảng trống trước x
• ret:=0
• tạo một ma trận dp có kích thước (n + 1) x (n + 1)
• cho tôi trong phạm vi từ 1 đến n
  • cho j trong phạm vi n đến n
    • dp [i, j]:=max of dp [i, j - 1], dp [i - 1, j]
    • nếu x [i] =s [j], thì dp [i, j]:=max của dp [i, j] và 1 + dp [i - 1, j - 1]
• trả về dp [n, n]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int longestPalindromeSubseq(string s) {
      string x = s;
      reverse(x.begin(), x.end());
      int n = s.size();
      if(!n) return 0;
      s = " " + s;
      x = " " + x;
      int ret = 0;
      vector < vector <int> > dp(n + 1, vector <int>(n + 1));
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= n ; j++){
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            if(x[i] == s[j]) {
               dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
            }
         }
      }
      return dp[n][n];
   }
};
main(){
   Solution ob;
   cout << (ob.longestPalindromeSubseq("bbbab"));
}

Đầu vào

"bbbab"

Đầu ra

4