Đếm tất cả dãy con palindrome trong xâu trong C++

Trong hướng dẫn này, ta sẽ thảo luận chương trình để tìm số lượng dãy con (subsequence) palindrome trong một xâu cho trước.

Cho một xâu. Nhiệm vụ là tìm số lượng dãy con palindrome có thể tạo ra từ xâu đó.

Ví dụ

#include <iostream>
#include <cstring>
using namespace std;

int count_palin(string str) {
    int N = str.length();
    vector<vector<int>> cps(N + 1, vector<int>(N + 1, 0));
    for(int i = 0; i < N; i++)
        cps[i][i] = 1;
    for(int L = 2; L <= N; L++) {
        for(int i = 0; i < N; i++) {
            int k = L + i - 1;
            if(k >= N) continue;
            if(str[i] == str[k])
                cps[i][k] = cps[i][k-1] + cps[i+1][k] + 1;
            else
                cps[i][k] = cps[i][k-1] + cps[i+1][k] - cps[i+1][k-1];
        }
    }
    return cps[0][N-1];
}

int main() {
    string str = "abcb";
    cout << "Total palindromic subsequence are: " << count_palin(str) << endl;
    return 0;
}

Kết quả

Total palindromic subsequence are: 6