杭电-oj Palindrome

翻译

Problem Description

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 which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome.As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome.回文是一个对称的字符串，也就是说，一个从左到右以及从右到左读取的字符串是相同的。 你要写一个程序，给定一个字符串，确定最小数量的字符要插入到字符串，以获得一个回文。 例如，通过插入2个字符，字符串“ ab3bd”可以转换为回文(“ dab3bad”或“ adb3bda”)。 然而，插入少于两个字符不会产生回文

Input

Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from 'A' to 'Z', lowercase letters from 'a' to 'z' and digits from '0' to '9'. Uppercase and lowercase letters are to be considered distinct.你的程序是从标准输入读取。 第一行包含一个整数: 输入字符串的长度 n，3<=n<= 5000。 第二行包含一个长度 n 的字符串，字符串由大写字母“ a”到“ z” ，小写字母“ a”到“ z”和数字“0”到“9”组成。 大写和小写字母是不同的

Output

Your program is to write to standard output. The first line contains one integer, which is the desired minimal number.

你的程序是写到标准输出。第一行包含一个整数，这是所需的最小数

Sample Input

5

Ab3bd

Sample Output

2

思路：

题目意思是要求添加多少个字符可以使字符串变为回文串，我们需要将序列本身和翻转之后的自己进行求最长公共子序列，因为回文串是需要左右对称，所以我们将字符串翻转后求最长公共子序列，可以找到前后有多少匹配的，将总长度减去匹配的，剩下的就是不匹配的，我们只需要添加不匹配的就可以了.

注意：最长公共子序列（longest common sequence）和最长公共子串（longest common substring）不是一回事儿

 

子序列：比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与母串保持一致，我们将其称为公共子序列。

 

子串：子串是要求更严格的一种子序列，要求在母串中连续地出现

 

 

代码：

 

总结：

本片参考我同学PPT，他可能参考别的博主了。侵权删。