回文字符串个数c++

在 C++ 中，计算给定文本中的回文子串的数量可以使用动态规划的方法。一个常见的问题是寻找所有长度为 k 的回文子串，而不仅仅是单个最长回文。以下是一个简单的例子，展示了如何使用滑动窗口技巧来解决这个问题：

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

int countPalindromes(string text, int k) {
    int n = text.size();
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
    
    // 初始化边界情况
    for (int i = 1; i <= n; i++) {
        dp[i][1] = (text[i - 1] == text[i - 1]);
    }
    
    // 动态规划核心算法
    for (int len = 2; len <= k; len++) {
        for (int i = 2; i <= n; i++) {
            if (text[i - 1] == text[i - len]) {
                dp[i][len] = dp[i - 1][len - 1];
            } else {
                dp[i][len] = dp[i - 1][len]; // 如果当前字符不匹配，则无法形成回文
            }
        }
    }
    
    // 统计长度为k的所有回文子串数量
    int count = 0;
    for (int i = 0; i <= n - k; i++) {
        count += dp[i + k][k];
    }
    
    return count;
}

int main() {
    string input = "babad";
    int k = 2;
    cout << "Number of palindromes of length " << k << " in the given text: " << countPalindromes(input, k) << endl;
    return 0;
}