首页 > ACM题库 > HDU-杭电 > hdu 2163 Palindromes-字符串处理-[解题报告]C++
2013
12-30

hdu 2163 Palindromes-字符串处理-[解题报告]C++

Palindromes

问题描述 :

Write a program to determine whether a word is a palindrome. A palindrome is a sequence of characters that is identical to the string when the characters are placed in reverse order. For example, the following strings are palindromes: “ABCCBA”, “A”, and “AMA”. The following strings are not palindromes: “HELLO”, “ABAB” and “PPA”.

输入:

The input file will consist of up to 100 lines, where each line contains at least 1 and at most 52 characters. Your program should stop processing the input when the input string equals “STOP”. You may assume that input file consists of exclusively uppercase letters; no lowercase letters, punctuation marks, digits, or whitespace will be included within each word.

输出:

The input file will consist of up to 100 lines, where each line contains at least 1 and at most 52 characters. Your program should stop processing the input when the input string equals “STOP”. You may assume that input file consists of exclusively uppercase letters; no lowercase letters, punctuation marks, digits, or whitespace will be included within each word.

样例输入:

ABCCBA
A
HELLO
ABAB
AMA
ABAB
PPA
STOP

样例输出:

#1: YES
#2: YES
#3: NO
#4: NO
#5: YES
#6: NO
#7: NO

这题是Rujia Liu推荐的第一个字符串题。

题意很容易看懂,就是给出字符串,判断其是否是回文或镜面对称回文。输出有4种情况,给出的表格做了很清楚的说明。

思路:写两个函数,is_palindrome()判断是否是回文串,is_mirrored()判断是否是镜像对称串。

第一个很好写,只要扫描字符串,首尾相比判断是否相等即可:

int is_palindrome(char *str)
{
	int i,len = strlen(str);
	for(i=0; i<len/2; i++)
	{
		if(str[i] != str[len-i-1])
			return 0;
	}
	return 1;
}

第二个函数is_mirrored(),这个函数是此题的核心问题

其实也不难写,有些细节问题要注意

首先可以用两个数组把题目中的表格存起来,我看有位同学用了20多个if else 尴尬太狠了,用数组存应该是比较好的办法了。

char const *ch = "AEHIJLMOSTUVWXYZ12358";
char const *re = "A3HILJMO2TUVWXY51SEZ8";

然后在函数内部首先要对只有一个字符的字符串进行特殊情况判断:

if(len == 1)
    {
        for(j=0; j<table_len; j++)
        {
            if(ch[j] == str[0])
                break;
        }
        if(j == 21 || re[j] != str[0])
            return 0;
    }

为什么不用在下面的主循环判断中通过修改判断条件(把i<len/2改为i<len/2+1,这样就比刚才多往后判断一个字符,可以排除len=1时循环一次也不执行的问题)for(i=0; i<len/2 + 1; i++)来排除这个特殊情况呢?

因为这样的话,在多个字符的字符串判定时,每次都要多扫一次,还不如这样来的好些(个人看法)

这个问题解决之后,那就没什么问题了,函数如下:

int is_mirrored(char *str)
{
	int table_len = strlen(ch);
	int i,j,len = strlen(str);
	if(len == 1)
	{
		for(j=0; j<table_len; j++)
		{
			if(ch[j] == str[0])
				break;
		}
		if(j == 21 || re[j] != str[0])
			return 0;
	}
	else if(len > 1)
	for(i=0; i<len/2; i++)
	{
		for(j=0; j<table_len; j++)
		{
			if(ch[j] == str[i])
				break;
		}	
		if(j == 21 || re[j] != str[len-i-1])
			return 0;
	}
	return 1;
}

=======================================================

遇到的问题:

(1)刚开始,把字符串定义为全局的之后,想着把它的长度也定为全局的吧,于是乎,就在main()函数外来了这么一句声明

int table_len = strlen(ch);

结果编译时报错:initializer element is not constant(用于初始化的元素不是一个常量)

什么情况呢?去网上查了下,原来如此:

======================以下转自ChinaUnix kiffa=======================

在C++中对于以下语句:
// 全局域
int i = 3;
int j = i;

编译时将i 放入.data 段,设置其值为3.

而对于j ,编译器遇到这种语句,只知道j = i ,由于 i 是变量,不是常量,编译器无法在编译时直接得到它的值,编译器只会找到i 的地址, 然后读取这个地址的内容,再把这个内容写入 j 的地址。

编译器不能够直接用3 来初始化 j ,因为计算机不是人,不懂简单的人类逻辑,我们想“因为 i = 3,而 j = i,所以j = 3",而计算机无法在逻辑上由i = 3 和 j = i 来推出j = 3,就好像图灵机不可能证明某个论题的真伪一样。

计算机只会“取 i 的地址,把3 放到 i 的地址中,取 i 的地址,读取这个地址中的内容,取 j 的地址,把这个内容 写入j 的地址。” 它不会思考,不懂因果,只是机械地执行指令。编译器无法在编译时求得一个非常量的值,它只能在运行时通过读取变量地址来间接得到变量的值,而全局变量在编译时就必须确定其值,故C有静态存储区数据必须用常量初始化的规定。

在编译时只能用常量去初始化一个静态存储区的数据,而不能用“读取某个变量的内容”来初始化,所以编译器会将j 放入 .bss段,默认值为0 ,然后添加一条语句在运行时读取i 的值,再赋给j。这条语句在调用main()之前完成。

一个对比:

对于语句:
int i = 3

int main()
{
    int j = i;
    …
}

在编译时不需要确定局部变量 j 的值,而是在运行时读取i 的值来赋给 j. 编译连接后的可执行文件中不会存放j 的值,只有相应的赋值语句的代码。与此相对的,由于i 是全局变量,存储在静态存储区,因此在编译时其值就需要确定其值,在目标文件中会分配空间来存放 i 的值,运行时不会有赋值语句来给 i 赋值, 没有对应的代码。

而对于语句:
int i = 3;
int j = i;

由于j 是全局变量,存储在静态存储区,因此也需要在编译时确定其值。而i 是变量,不是常量,i 的值无法在编译时确定,这就造成j 的值也无法在编译时确定,所以C对此就会报错。而C++采取了另外一种做法,在编译时简单的把 j 作为未初始化的全局变量放入.bss 区,其默认值为0,然后添加一条语句在运行时给 j 赋值,并保证这条语句在 main函数开始之前执行。因此j 的初始化实际上实在运行时完成的。

===================================感谢kiffa的分享=====================

后来把这条声明语句放到is_mirrored()内之后问题解决

(2)上面说过了,就是忘了考虑单个输入的问题。修正此问题后就AC了

下面是我的代码:

/**
 * Author: Gneveek
 * Data: 2011-10-2
 * Descripition:  UVa 401 - Palindromes
 */ 
#include <stdio.h>
#include <string.h>
#define MAXN 1024
char const *ch = "AEHIJLMOSTUVWXYZ12358";
char const *re = "A3HILJMO2TUVWXY51SEZ8";

int is_palindrome(char *str)
{
	int i,len = strlen(str);
	for(i=0; i<len/2; i++)
	{
		if(str[i] != str[len-i-1])
			return 0;
	}
	return 1;
}

int is_mirrored(char *str)
{
	int table_len = strlen(ch);
	int i,j,len = strlen(str);
	if(len == 1)
	{
		for(j=0; j<table_len; j++)
		{
			if(ch[j] == str[0])
				break;
		}
		if(j == 21 || re[j] != str[0])
			return 0;
	}
	else if(len > 1)
	for(i=0; i<len/2; i++)
	{
		for(j=0; j<table_len; j++)
		{
			if(ch[j] == str[i])
				break;
		}	
		if(j == 21 || re[j] != str[len-i-1])
			return 0;
	}
	return 1;
}


int main()
{
	//freopen("C:\\in.txt","r",stdin);
	char str[MAXN];	
	while(scanf("%s",str) != EOF)
	{
		if(is_palindrome(str))
		{
			if(is_mirrored(str))
				printf("%s -- is a mirrored palindrome.\n\n",str);
			else
				printf("%s -- is a regular palindrome.\n\n",str);
		}
		else
		{
			if(is_mirrored(str))
				printf("%s -- is a mirrored string.\n\n",str);
			else
				printf("%s -- is not a palindrome.\n\n",str);
		}
	}
	return 0;
}

解题转自:http://blog.csdn.net/gneveek/article/details/6840471


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。