输入一个字符串,求其中最长回文子串。子串的含义是:在字符串中连续出现的字符串片段。回文的含义是:正着看和倒着看是相同的,如abba和abbebba,在判断时要求忽略所有的标点和空格,且忽略大小写,但输出时按原样输出(首尾不要输出多余的字符串)。输入字符串长度大于等于1小于等于5000,且单独占一行。
时间: 2024-03-27 11:36:03 浏览: 169
好的,我来给你提供一份 C 语言代码来实现这个功能。代码如下:
```
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAXN 5005
char s[MAXN], t[MAXN << 1];
int p[MAXN << 1];
int main() {
fgets(s, MAXN, stdin); // 读入字符串
int n = strlen(s), len = 0;
for (int i = 0; i < n; ++i) { // 将字符串中的字符转化为小写字母
if (isalpha(s[i])) t[len++] = tolower(s[i]);
}
int mx = 0, id = 0;
n = len * 2 + 2;
t[n - 1] = '\0';
t[n - 2] = '#'; // 插入分隔符 #
for (int i = 0; i < len; ++i) { // 插入空格和字符
t[i * 2] = '#';
t[i * 2 + 1] = t[i];
}
for (int i = 1; i < n; ++i) { // 计算回文半径
if (i < mx) p[i] = p[id * 2 - i] < mx - i ? p[id * 2 - i] : mx - i;
else p[i] = 1;
while (t[i - p[i]] == t[i + p[i]]) ++p[i];
if (mx < i + p[i]) {
mx = i + p[i];
id = i;
}
}
int pos = 0, max_len = 0;
for (int i = 1; i < n; ++i) { // 找到最长回文子串
if (p[i] > max_len) {
max_len = p[i];
pos = i;
}
}
int start = (pos - max_len + 1) / 2; // 计算最长回文子串在原字符串中的位置
for (int i = start; i < start + max_len; ++i) {
printf("%c", s[i]);
}
printf("\n");
return 0;
}
```
这里使用了 Manacher 算法来求解最长回文子串。时间复杂度为 $O(n)$。
阅读全文