输出字符串中最长回文串的长度。 用c编写
时间: 2023-03-27 08:01:36 浏览: 89
回文串是指正反读都一样的字符串。要求输出字符串中最长回文串的长度,可以使用以下方法:
1. 暴力法:
对于每一个字符,都从这个字符开始,向两边扩展,判断是否为回文串。如果是,则继续扩展,直到不是回文串为止。最后记录下最长回文串的长度即可。时间复杂度为 O(n^3)。
下面是 C 语言代码示例:
```c
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
char s[100];
scanf("%s", s);
int len = strlen(s);
int max_len = 0;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
int k;
for (k = 0; k <= j - i; k++) {
if (s[i + k] != s[j - k]) {
break;
}
}
if (k > max_len) {
max_len = k;
}
}
}
printf("%d\n", max_len - 1);
return 0;
}
```
2. Manacher 算法:
Manacher 算法是一种时间复杂度为 O(n) 的算法,可以用来求出字符串中最长回文子串的长度。
下面是 C 语言实现的代码示例:
```c
#include <stdio.h>
#include <string.h>
char s[200005];
int p[200005];
int cnt[200005];
int main() {
scanf("%s", s + 1);
int len = strlen(s + 1);
int mx = 0, id = 0;
for (int i = 1; i <= len; i++) {
if (mx > i) {
p[i] = min
阅读全文