最长回文串 Description 给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。 Input 输入：长度不大于100的非空字符串s，区分大小写. Output 输出： 字符串s中包含的最长回文串的长度. Sample Input 1 ab Sample Output 1 1用c语言实现

### 寻找字符串中最长回文子串的长度 为了计算给定字符串中的最长回文子串长度，可以采用中心扩展法的思想。这种方法通过遍历字符串中的每一个可能的中心点，并向两侧扩展以找到最大的回文子串。 以下是基于此方法的一个完整的 C 语言实现： #### 实现代码 ```c #include <stdio.h> #include <string.h> // 辅助函数：从指定中心向外扩展并返回最大回文子串的长度 int expandAroundCenter(const char* s, int left, int right) { int L = left; int R = right; int n = strlen(s); while (L >= 0 && R < n && s[L] == s[R]) { // 扩展条件 L--; R++; } return R - L - 1; // 返回当前回文子串的长度 } // 主函数：寻找最长回文子串的长度 int longestPalindromeLength(const char* s) { if (s == NULL || strlen(s) == 0) return 0; int start = 0, end = 0; // 起始和结束位置 int maxLen = 0; // 当前已知的最大回文子串长度 int n = strlen(s); for (int i = 0; i < n; i++) { // 奇数长度回文子串 int len1 = expandAroundCenter(s, i, i); // 偶数长度回文子串 int len2 = expandAroundCenter(s, i, i + 1); // 取两种情况下的较大值 int currentMax = len1 > len2 ? len1 : len2; // 更新全局最大值及其对应的起始/结束位置 if (currentMax > maxLen) { maxLen = currentMax; start = i - (maxLen - 1) / 2; // 新起点 end = i + maxLen / 2; // 新终点 } } return maxLen; // 返回最终的结果 } int main() { const char str[] = "babad"; // 测试字符串 printf("Longest palindrome length is %d\n", longestPalindromeLength(str)); return 0; } ``` #### 解析 1. **辅助函数 `expandAroundCenter`** 此函数用于从某个中心点出发，逐步向左右两边扩展，直到不再满足回文性质为止。它接受两个索引参数（可能是相同的），分别表示潜在回文子串的左侧和右侧边界[^1]。 2. **主逻辑部分** 对于输入字符串中的每个字符，尝试将其作为奇数长度回文子串的中心；同时也考虑偶数长度的情况（即相邻两字符为中心）。每次调用 `expandAroundCenter` 后更新最大回文子串的信息。 3. **复杂度分析** 时间复杂度为 \(O(n^2)\)，其中 \(n\) 是字符串的长度。这是因为对于每个字符都进行了最多 \(O(n)\) 的扩展操作。 --- ###