ZJU 2744 解题报告

Palindromes

Time Limit: 1 Seconds Memory Limit: 32768 KB

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.

Input

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.

Output

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

Sample Input

aba
aa

Output for Sample Input

4
3

Source: Zhejiang Provincial Programming Contest 2006

没什么技巧可言,依次枚举每个字符作为中心,往两边拓展就可以了,分别统计回文长度为奇数和偶数两种情况.接近于纯暴力的搜索.

CODE

#include<stdio.h>
#include<string.h>
 
int main()
{
  int i, j, k, len ,cnt;
  char s[5005];
  while (scanf("%s", s) != EOF)
    {
      len = strlen(s);
      cnt = len;
      i = -1;
      while (s[++i])
        {
          //回文长度为奇数
          for(j = 1; i - j >= 0 && i + j < len; ++j)
            {
              if( s[i - j] == s[i + j] )
                ++cnt;
              else
                break;
            }
          //回文长度为偶数
          for(j = 1; i - j + 1 >= 0 && i + j < len; ++j)
            {
              if( s[i - j + 1] == s[i + j] )
                ++cnt;
              else
                break;
            }
        }
      printf("%d\n", cnt);
    }
  return 0;
}
» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:

Leave a Comment

NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>