首页 > ACM题库 > HDU-杭电 > HDU 1544 Palindromes-枚举-[解题报告] C++
2013
12-12

HDU 1544 Palindromes-枚举-[解题报告] C++

Palindromes

问题描述 :

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

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1544

思路:枚举中间点,分为奇数长度和偶数长度,然后向两边扩展就可以了,如果不相等,就直接跳出;

#include<iostream>
 #include<cstdio>
 #include<cstring>
 using namespace std;
 #define MAXN 5005
 char str[MAXN];
 
 int main(){
     while(~scanf("%s",&str)){
         int len=strlen(str),l,r;
         int ans=len;
         for(int i=0;i<len;i++){
             l=i-1,r=i+1;//奇数长度
             while(l>=0&&r<len&&str[l]==str[r]){
                 l--,r++;
                 ans++;
             }
             l=i,r=i+1;//偶数长度
             while(l>=0&&r<len&&str[l]==str[r]){
                 l--,r++;
                 ans++;
             }
         }
         printf("%d\n",ans);
     }
     return 0;
 }

 

解题报告转自:http://www.cnblogs.com/wally/archive/2013/05/20/3089902.html


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  3. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept