字符数组2

103 阅读 0 评论 68 点赞

我是靠谱客的博主愉快秋天，这篇文章主要介绍字符数组2，现在分享给大家，希望可以做个参考。

输入一个字符串，求出其中最长的回文字串。
忽略所有标点符号和空格，忽略大小写，输出保持原样。
输入字符串长度不超过5000，占据单独一行。
输出最长的回文串，如果有多个，输出起始位置最靠左的。

分析：
1.首先不能用scanf，因为它碰到空格或者TAB就会停止。
用fgets(buf,MAXN,stdin)，它会读取不超过MAXN-1个字符，然后在末尾添上’’，读到’n’就停止。如果一个字符都没有读到，返回NULL。
gets(s)也能读，但是它没有指明最大字符数，有可能存在缓冲区溢出，不推荐使用。
2.预处理，利用原字符串构造一个新的字符串（没有空格和标点，且全部变成大写）。
3.用一个数组p保存字符s[i]在buf中的位置，输出用。
4.从左到右扫，用max记录最长回文，枚举回文串的中间位置i，然后不断往外扩展，直到有字符不同。

复制代码

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#define MAXN 5000 + 10
char buf[MAXN], s[MAXN];
int p[MAXN];

int main()
{
    int n, m = 0, max = 0, x, y;
    int i, j;
    fgets(buf, sizeof(s), stdin);
    n = strlen(buf);
    for (i = 0; i < n; i++)
        if (isalpha(buf[i]))
        {
            p[m] = i;
            s[m++] = toupper(buf[i]);       //原字符串保存到s中 m是s的长度
        }
    for (i = 0; i < m; i++)
    {
        for (j = 0; i - j >= 0 && i + j < m; j++)   //处理长度为奇数的
        {
            if (s[i - j] != s[i + j])
                break;
            if (j * 2 + 1 > max)
            {
                max = j * 2 + 1;
                x = p[i - j];
                y = p[i + j];
            }
        }
        for (j = 0; i - j >= 0 && i - j + 1 < m; j++)  //处理长度为偶数的
        {
            if (s[i - j] != s[i - j + 1])
                break;
            if (j * 2 + 2 > max)
            {
                max = j * 2 + 2;
                x = p[i - j];
                y = p[i + j + 1];
            }
        }
    }
    for (i = x; i <= y; i++)
        printf("%c", buf[i]);
    printf("n");
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#define MAXN 5000 + 10
char buf[MAXN], s[MAXN];
int p[MAXN];

int main()
{
    int n, m = 0, max = 0, x, y;
    int i, j;
    fgets(buf, sizeof(s), stdin);
    n = strlen(buf);
    for (i = 0; i < n; i++)
        if (isalpha(buf[i]))
        {
            p[m] = i;
            s[m++] = toupper(buf[i]);       //原字符串保存到s中 m是s的长度
        }
    for (i = 0; i < m; i++)
    {
        for (j = 0; i - j >= 0 && i + j < m; j++)   //处理长度为奇数的
        {
            if (s[i - j] != s[i + j])
                break;
            if (j * 2 + 1 > max)
            {
                max = j * 2 + 1;
                x = p[i - j];
                y = p[i + j];
            }
        }
        for (j = 0; i - j >= 0 && i - j + 1 < m; j++)  //处理长度为偶数的
        {
            if (s[i - j] != s[i - j + 1])
                break;
            if (j * 2 + 2 > max)
            {
                max = j * 2 + 2;
                x = p[i - j];
                y = p[i + j + 1];
            }
        }
    }
    for (i = x; i <= y; i++)
        printf("%c", buf[i]);
    printf("n");
    return 0;
}