Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 12thIOI第一天试题一
发信站: 哈工大紫丁香 (2001年06月14日15:36:28 星期四), 站内信件

Palindrome
PROBLEM
A palindrome is a symmetrical string, that is, a string read identically from
 left to right as well as from right to left.  You are to write a program whi
ch, given a string, determines the minimal number of characters to be inserte
d into the string in
order to obtain a palindrome.
As an example, by inserting 2 characters, the string "Ab3bd" can be transform
ed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than
2 characters does not produce a palindrome.
INPUT
The input file name is PALIN.IN. The first line contains one integer: the len
gth of the input string N, 3￡N￡5000. The second line contains one string wi
th length N. The string is formed from uppercase letters from 'A' to 'Z', low
ercase letters from
'a' to 'z' and digits from '0' to '9'. Uppercase and lowercase letters are to
 be considered distinct.
OUTPUT
The output file name is PALIN.OUT. The first line contains one integer, which
 is the desired minimal number.
EXAMPLE INPUT AND OUTPUT

PALIN.IN                                        PALIN.OUT

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]