C++ 最长对称子串算法实现

#include #include using namespace std;

// 计算给定字符串中最长的对称子串的长度 int longestSymmetricSubstring(string str) { int n = str.length(); int maxLength = 1; // dp[i][j] 表示 str[i:j] 是否是对称子串 bool dp[1000][1000] = {false};

// 所有长度为 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;
        // 如果首尾字符相等且剩余子串是对称的，则当前子串也是对称的
        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; }

// 程序功能：计算给定字符串中最长的对称子串的长度。 // 算法思路：使用动态规划，通过一个二维数组记录子串是否对称。 // 遍历所有可能的子串长度和起始位置，判断子串是否对称，更新最长对称子串的长度。 // 复杂度分析：时间复杂度 O(n^2)，空间复杂度 O(n^2)。