首页给定一个字符串，求它的最长回文子串的长度，C语言实现

给定一个字符串，求它的最长回文子串的长度，C语言实现

时间: 2023-02-07 19:21:26 浏览: 197

您好，可以使用 Manacher 算法来求解最长回文子串的长度。该算法的时间复杂度为 O(n)，并且可以在线性时间内找到所有回文子串的起始位置。下面是 C 语言的实现方法： ``` #include <stdio.h> #include <string.h> #define max(a, b) ((a) > (b) ? (a) : (b)) char str[100010]; int p[100010]; int main() { scanf("%s", str + 1); int n = strlen(str + 1); int mx = 0, id = 0; for (int i = 1; i <= n; i++) { if (mx > i) p[i] = min(p[(id << 1) - i], mx - i); else p[i] = 1; while (str[i - p[i]] == str[i + p[i]]) p[i]++; if (p[i] + i > mx) { mx = p[i] + i; id = i; } } int ans = 0; for (int i = 1; i <= n; i++) ans = max(ans, p[i] - 1); printf("%d\n", ans); return 0; } ``` 希望这对您有帮助！

阅读全文