C++ 计算最长对称子串长度

// 该程序用于计算给定字符串中最长的对称子串的长度 #include #include using namespace std;

// 定义函数，计算最长对称子串的长度 int longestSymmetricSubstring(string str) { int n = str.length(); // 获取字符串的长度 int maxLength = 1; // 初始化最长对称子串的长度为1 bool dp[1000][1000] = {false}; // 定义一个二维数组用于存储状态，dp[i][j]表示从第i个字符到第j个字符是否是对称子串

// 初始化状态，每个字符本身可以看作是长度为1的对称子串
for (int i = 0; i < n; i++) {
    dp[i][i] = true;
}

// 动态规划计算状态
for (int len = 2; len <= n; len++) { // 遍历所有可能的子串长度
    for (int i = 0; i < n - len + 1; i++) { // 遍历所有可能的子串起始位置
        int j = i + len - 1; // 子串的结束位置
        // 如果子串的首尾字符相等，且去掉首尾字符后的子串也是对称子串或者子串长度为2，则该子串也是对称子串
        if (str[i] == str[j] && (len == 2 || dp[i+1][j-1])) {
            dp[i][j] = true; // 更新状态
            maxLength = max(maxLength, len); // 更新最长对称子串的长度
        }
    }
}

return maxLength; // 返回最长对称子串的长度

}

int main() { string str; getline(cin, str); // 从标准输入中获取字符串 int length = longestSymmetricSubstring(str); // 调用函数计算最长对称子串的长度 cout << length << endl; // 输出最长对称子串的长度 return 0; }