Đếm tất cả xâu 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 xâu con (substring) palindrome trong một xâu.

Cho một xâu. Nhiệm vụ là đếm số xâu con palindrome có độ dài lớn hơn 1 (hoặc theo đề bài gốc là > 3, nhưng code đếm tất cả).

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int count_pstr(char str[], int n) {
    vector<vector<int>> dp(n, vector<int>(n, 0));
    vector<vector<bool>> P(n, vector<bool>(n, false));
    for(int i = 0; i < n; i++)
        P[i][i] = true;
    for(int i = 0; i < n-1; i++) {
        if(str[i] == str[i+1]) {
            P[i][i+1] = true;
            dp[i][i+1] = 1;
        }
    }
    for(int gap = 2; gap < n; gap++) {
        for(int i = 0; i + gap < n; i++) {
            int j = i + gap;
            if(str[i] == str[j] && P[i+1][j-1])
                P[i][j] = true;
            if(P[i][j])
                dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1 - dp[i+1][j-1];
            else
                dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
        }
    }
    return dp[0][n-1];
}

int main() {
    char str[] = "abaab";
    int n = strlen(str);
    cout << count_pstr(str, n) << endl;
    return 0;
}

Kết quả

3