当前位置: 代码迷 >> C语言 >> 超难的题目。看看有谁可以解决
  详细解决方案

超难的题目。看看有谁可以解决

热度:305   发布时间:2006-07-22 13:36:32.0
超难的题目。看看有谁可以解决

拿破仑的自嘲

Time Limit:5000MS Memory Limit:65536K
Total Submit:2 Accepted:1

Description

Legend has it that, after being defeated in Waterloo, Napoleon Bonaparte, in retrospect of his days of glory, talked to himself "." Although, it is quite doubtful that he should have said this in English, this phrase is widely known as a typical palindrome.
A palindrome is a symmetric character sequence that looks the same when read backwards, right to left. In the above Napoleon's grumble, white spaces appear at the same positions when read backwards. This is not a required condition for a palindrome. The following, ignoring spaces and punctuation marks, are known as the first conversation and the first palindromes by human beings.

有这样一个传说:拿破仑在滑铁卢被击败后,回顾他的辉煌时代时,自言自语:“Able was I ere I saw Elba.”。虽然,对于他应该用英语来说这句话有点疑问,但这句话因为是典型的回文而广为人知。(注:中文回文的例子:人过大佛寺,寺佛大过人)
回文指的是前后读相同的中心对称的字符序列。在上面提到的拿破仑的自嘲中,当从后往前读时,空格也在相同的位置。对于回文来说,这个不作为要求的条件。下面是人类熟知的第一个对话也是第一个回文,忽略空格和标点符号:

"Madam, I'm Adam."
"Eve."
(by Mark Twain 马克 吐温)

Write a program that finds palindromes in input lines.
编写一个程序找出在输入行中的回文。

Input

A multi-line text is given as the input. The input ends at the end of the file.

There are at most 100 lines in the input. Each line has less than 1,024 Roman alphabet characters.

给出一个多行的文本作为输出,输入数据到文件末尾结束。

在输入中最多100行。每一行少于1024个罗马字母。

Output

Corresponding to each input line, a line consisting of all the character sequences that are palindromes in the input line should be output. However, trivial palindromes consisting of only one or two characters should not be reported.

对于每个输入行,要求输出这样一行:输入行中是回文的所有字符序列。

On finding palindromes, any characters in the input except Roman alphabets, such as punctuation characters, digits, spaces, and tabs, should be ignored. Characters that differ only in their cases should be looked upon as the same character. Whether or not the character sequences represent a proper English word or sentence does not matter.

在寻找回文时,输入行中的除了罗马字母以外的其他字符,比如标点符号,数字,空格,和tab符号,全部忽略。只是大小写不同的字符要作为相同的字符。不考虑这个字符序列是否为英文单词或句子。

Palindromes should be reported all in uppercase characters. When two or more palindromes are reported, they should be separated by a space character. You may report palindromes in any order.

全部用大写字母来输出回文。当输出两个或更多回文时,应该用空格分隔。你可以用任意顺序输出回文。

If two or more occurrences of the same palindromes are found in the same input line, report only once. When a palindrome overlaps with another, even when one is completely included in the other, both should be reported. However, palindromes appearing in the center of another palindrome, whether or not they also appear elsewhere, should not be reported. For example, for an input line of "AAAAAA", two palindromes "AAAAAA" and "AAAAA" should be output, but not "AAAA" nor "AAA". For "AAABCAAAAAA", the output remains the same.

如果在一个输入行中发现了两个或多个相同的回文,只输出一个。当一个回文与另一个回文交迭时,即使一个完全包括在另一个中,也应该输出两个。但是,当一个回文出现在另一个回文的中心部位时,无论是否也在其他位置出现,就不应该输出这个回文。比如,对于输入行"AAAAAA",应该输出两个回文“AAAAAA"和“AAAAA”,但不应该输出“AAAA”和“AAA”。对于“AAABCAAAAAA”,输出也是同样。

One line should be output corresponding to one input line. If an input line does not contain any palindromes, an empty line should be output.

对于每一个输入行,应该输出一行。如果一个输入行不包括一个回文,应该输出一个空行。


Sample Input


As the first man said to the
first woman:
"Madam, I'm Adam."
She responded:
"Eve."

Sample Output


TOT

MADAMIMADAM MADAM
ERE DED
EVE

注意:Note that the second line in the output is empty, corresponding to the second input line containing no palindromes. Also note that some of the palindromes in the third input line, namely "ADA", "MIM", "AMIMA", "DAMIMAD", and "ADAMIMADA", are not reported because they appear at the center of reported ones. "MADAM" is reported, as it does not appear in the center, but only once, disregarding its second occurrence.
注意:因为对应的第二个输入行中不包含回文,第二个输出行是空行。也要注意第三个输入行中的某几个回文,即“"ADA", "MIM", "AMIMA", "DAMIMAD", and "ADAMIMADA"不能被输出,因为它们处于已经输出的几个回文中的中心。“MADAM”被输出,因为它没有出现在中心位置,但必须抛弃第二次的情况,而只输出一次。

Source

Tokyo98-d


----------------解决方案--------------------------------------------------------
  相关解决方案