Palindromes

Palindromes

时间: 1ms        内存:64M

描述:

A regular palindrome is a string of numbers or letters that is the same forward as backward. For example, the string "ABCDEDCBA" is a palindrome because it is the same when the string is read from left to right as when the string is read from right to left.

Now give you a string S, you should count how many palindromes in any consecutive substring of S.

输入:

There are several test cases in the input. Each case contains a non-empty string which has no more than 5000 characters.

Proceed to the end of file.

输出:

A single line with the number of palindrome substrings for each case.

示例输入:

aba
aa

示例输出:

4
3

提示:

参考答案(内存最优[752]):

#include <stdio.h>
int main()
{
    int i,j,k,g,n,h;
    char a[5005];
    while(scanf("%s",a)!=EOF)
    {
        k=strlen(a);
        h=k;
        for(i=1; i<k; i++)
        {
            for(n=0; n<k; n++)
            {
                g=n+i;
                if (g>k)
                    break;
                for(j=n; j<=(n+i); j++)
                {
                    if (a[j]!=a[g])
                        break;
                    if (j==(n+i))
                        h++;
                    g--;
                }
            }

        }
        printf("%d\n",h);
    }
    return 0;
}

参考答案(时间最优[0]):

#include <stdio.h>
int main()
{
    int i,j,k,g,n,h;
    char a[5005];
    while(scanf("%s",a)!=EOF)
    {
        k=strlen(a);
        h=k;
        for(i=1; i<k; i++)
        {
            for(n=0; n<k; n++)
            {
                g=n+i;
                if (g>k)
                    break;
                for(j=n; j<=(n+i); j++)
                {
                    if (a[j]!=a[g])
                        break;
                    if (j==(n+i))
                        h++;
                    g--;
                }
            }

        }
        printf("%d\n",h);
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注