tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 学科竞赛 >>

回文词


回专题模式 回学习阶段模式 【题目名称、来源】 回文词 ioi2000 【问题描述】 回文词是一种对称的字符串——也就是说, 一个回文词, 从左到右读和从右到左读得到 的 结果是一样的。任意给定一个字符串,通过插入若干字符,都可以变成一个回文词。你 的任务是写 一个程序,求出将给定字符串变成回文词所需插入的最少字符数。 比如字符串“ Ab3bd ” ,在插入两个字符后可以变成一个回文词( “ dAb3bAd ”或 “Adb3bdA” ) 。 然而,插入两个以下的字符无法使它变成一个回文词。 [输入] 输入文件的文件名是 PALIN.IN。 文件的第一行包含一个整数 N,表示给定的字符串的长度,3≤N≤5000。 文件的第二行是一个长度为 N 的字符串。字符串仅由大写字母“A”到“Z” ,小写字 母“a”到 “z”和数字“0”到“9”构成。大写字母和小写字母将被认为是不同的。 [输出] 输出文件名是 PALIN.OUT,文件只有一行,包含一个整数,表示需要插入的最少字符 数。 [输入输出样例] palin.in 5 Ab3bd palin.out 2 【所属专题】 动态规划 【适合学习阶段】 【解题思路】 问题分析:这个问题很简单,因为回文词左右是对称的,而对于一个不是回文词的字符 串,例如 Ab3bd,我们可以从这个字符串中的某一处断开,左子串不变,右子串变成倒序, 然后看两个串的最长公共子序列多长, 最长公共子序列是不需要再加入另外一个串中的。 但 是其他的字符需要加入到另一个串中。 所以问题就变成了求最长公共子序列。 但是需要注意 枚举每一个断开位置。 存储结构: 【测试数据】 【源程序】



推荐相关:

Palindrome 英文当中的回文词和回文句

182. 千古绝妙回文词 1页 2下载券 英文presentation 用词用... 11页 1下载...英​文​当​中​的​回​文​词​组​合​和​巧​夺...


奇妙的汉语(叠韵,连绵词,回文词)

回文词: (1)同义或近义:皇帝--帝皇,暴风--风暴,储存--存储,积累--累积,合适--适合,属下-下属,法律--律法,灵魂--魂灵,感情--情感,离别--别离,领头--...


文献学

文献学 - 宋代回文词浅谈 摘要, 关键词, 回文诗词多收入南宋桑世昌的《回文类聚》,《四库全书总目提要》 在一番溯源和指出此书疏漏之后,言及回文的价值,以为...


回文诗浅谈

回文诗浅谈 - 在杂体诗中,回文诗是颇负盛名的一类。回文诗,据唐代吴兢《乐府古题要解》的释义是:“回文诗,回复读之,皆歌而成文也。”回文,也写作“回文”...


退修信

退修信 - 退修信 《历代回文诗词选》退修信 ---同志: 您好!尊稿《历代回文诗词选》已拜读,甚佩。回文诗词为循汉字性能所创的特殊诗体,诚 可赏心怡情。...


回文:检测并输出一个文档中的回文单词

二、具体要求编写一个程序来解决一个文档中单词的回文问题, 该程序必须有判断一个单 词是否是回文单词的功能, 因此它应将文档分解成一个一个单词来进行判断并输...


课程设计:回文:检测并输出一个文档中的回文单词。用栈...

回文单词就是逐个字 母从前往后拼与从后往前拼得出的单词是一样的,如:1、121...DTCC2014:百分点内存数... 百度认证SEM02关键词优化...1/2 相关文档推荐 ...


回文问题:检测并输出一个文档中的回文单词。(要求用栈...

编写一个程序来解决一个文档中单词的回文问题,该程序必须 有判断一个单词是否是回文单词的功能, 因此它应该有将文档分解成一个一个单 词来进行判断并输出。根据...


如何在英语课堂上进行生动有效的词汇教学

3.单词中回文词的结构美 英语单词中,有些词顺着读和逆着读意思一样,如“noon”(正午); 有些单词顺着读和逆着读意思不一样。 “god” 如 (上帝)、“dog...


实验4-函数与指针

题目描述: 许多英语单词无论是顺读还是倒读,其词形完全一样,都是同一个单词,如 dad(爸爸) 、 noon(中午) 、level(水平)等,这样的词称为回文词。在最权威...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com