首页最长回文子串C语言怎么写

最长回文子串C语言怎么写

时间: 2023-03-09 18:12:04 浏览: 177

答案: 可以使用动态规划的方法来解决最长回文子串问题。具体的实现代码如下： int longestPalSubstr(char str[]) { // 首先初始化一个二维数组，值全部为false int n = strlen(str); bool table[n][n]; memset(table, 0, sizeof(table)); // 将对角线上的值全部设置为true int maxLength = 1; for (int i = 0; i < n; ++i) table[i][i] = true; // 将子串长度为2的情况检查 int start = 0; for (int i = 0; i < n-1; ++i) { if (str[i] == str[i+1]) { table[i][i+1] = true; start = i; maxLength = 2; } } // 以长度3开始，检查子串 for (int k = 3; k <= n; ++k) { // 检查子串的起始位置 for (int i = 0; i < n-k+1 ; ++i) { // 检查子串的结束位置 int j = i + k - 1; // 检查子串是否为回文 if (table[i+1][j-1] && str[i] == str[j]) { table[i][j] = true; if (k > maxLength) { start = i; maxLength = k; } } } } printf("最长回文子串为 %s ，长度为 %d", str+start, maxLength); return maxLength; // 返回最长回文子串长度 }

阅读全文