• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ2525 – Text Formalization

    ACM-POJ EXP 230阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    首先说明,下面所述的“大致题意”并不是题目的原意,但是按照题目原意去做是不可能AC的,因为测试数据库与题目原意出入非常大。另外顺便建议,刚玩POJ的同学没事不要做这题,因为如果没有测试数据库你会疯掉的,有测试数据库也很容易疯掉的。


    有两种类型的字符串,分别为Contraction和Acronym,它们都有其扩展形式Expand。现在给出C个Contraction和A个Acronym的扩展形式,格式如下:

    “contraction or acronym” -> “expansion”

    其中红色部分,引号和箭号之间可能有空格,可能无空格。

    然后再给出数篇Text,每篇Text用一个独占一行的#分隔(注意若有数个#连续出现,则不是分隔符),而且每篇Text都包含有数行,每行的长度最多为80。

    要求把每篇Text出现Contraction和Acronym的位置都分别用其扩展式替换,然后重新输出扩展后的Text。


    关于扩展:

    1、 Contraction

    Contraction在Text中有3种表现形式,按照优先级分别为”as listed,”(原型) “uppercased,”(尽数大写) 和 “capitalized.”(首字母大写)。

    举例说明: 给定Contraction为isn’t,其扩展式为is not

    那么在检测Text时,若检测到isn’t,则替换为is not

      若检测到ISN’T,则替换为IS NOT

      若检测到Isn’t,则替换为Is not

    若检测到诸如IsN’t的其他串,由于不属于以上3种情况的任意一种,则不替换,直接输出原串。

    注意

    (a)3种形式必须根据优先级检测,即若有”as listed,”,则不能替换为”uppercased,”或”capitalized.” ;若有”uppercased,”则不能替换为”capitalized.”。

    (b)扩展式与Contraction的表现形式必须一致。

    2、Acronym

    Acronym在Text中只有一种表现形式,就是”as listed,”,但替换时有2个特殊要求:

    (a) 对于同一篇Text,Acronym只能被替换1次,且替换的位置为其第一次出现的位置,其他位置不替换。

    (b) 替换Acronym的时候,必须在其替换式的最后加上“空格(Acronym原型)”。

    例如:给定Acronym为CS,其扩展式为Computing Science

    那么应该把Text中的CS替换为 Computing Science (CS)

    3、非字母串的Contraction与Acronym

    前2点都是在Contraction与Acronym都是由字母组成的基础上的替换模式。

    当Contraction或Acronym由非字母的字符串构成时,其扩展式只有”as listed,”一种形式,而Acronym替换后依然要加上“空格(Acronym原型)”。

    例如:

    (a)给定的Contraction为 <!=> ,其扩展式为a-c+d

    那么在Text检测到<!=>就直接替换为a-c+d,无大小写之分。

    (b) 给定Acronym为&&&,其扩展式为 **rr!! 那么在Text检测到&&&就直接替换为**rr!! (&&&)

    4、Contraction与Acronym可以是任意字符串的前缀或后缀,依然要替换

    5、不能迭代替换,就是说只能针对原本属于Text的字符串替换,不能对扩展后的Expand串替换

    解题思路

    其实如果原题题意和测试数据库的测试项是一致的话,这题是很简单的模拟题字符串替换而已,不应该放到“高级题”里面。


    原题题意故意误导的错误信息有3点:(注意下面是错误信息

    1、 Contraction与Acronym不是任何单词的前缀或后缀

    2、 Text是规范的字母串+标点

    3、”contraction or acronym” -> “expansion” 红色部分两引号间固定有2个空格


    而从测试数据库真正反应出来的信息是:(注意下面是正确信息

    1、Contraction与Acronym可以是任何字符(串)的前缀或后缀

    2、Text纯粹是一些字符串的组合

    3、”contraction or acronym” -> “expansion”红色部分两个引号之间的空格数目不固定


    明白到上面所述,本题的处理就很简单了。由于要匹配的字符串很多,因此本题用TrieTree的效率是最高的, hash很可能会超时。

    1、 把Contraction与Acronym录入到TrieTree,这里的TrieTree要做一个简单的变形,就是原本在结点中用于标记单词的布尔量flag,改为整型id,id=0表示从TrieTree到当前结点的字符串不是Contraction或Acronym; id>0表示TrieTree到当前结点的字符串是Contraction或Acronym,并且id就是其扩展式的映射。

    2、 建立扩展串二维数组,行为id,对应的行就是Contraction或Acronym的扩展式。

    3、 下面称上述2步为“字典录入”,字典录入的时候,在录入Contraction时,顺便同时录入其3种形式,而且必须按照优先顺序录入id。而这样录入可能会导致后面录入时出现重复,为了保证优先性,若在录入某个Contraction或Acronym时,该位置的id已经不为0,则跳过不录入,避免优先级低的扩展串替换了优先级高的扩展串。

    4、 在录入Acronym的时候,当存放其扩展串都Expand时,顺便把“空格(Acronym原型)”放到其扩展串末尾。

    5、 因此检测Text时,对Acronym的id设置标记是否扩展过一次,扩展过的不再扩展,当读入下一篇Text时(#号),标记清零。

    6、 对Text逐行读入,逐行替换后输出。由于Contraction与Acronym可以是任意字符串的前缀或后缀,对每一行的检测应该逐个字符检测,即对于字符c,若TrieTree中以c为首的字符串的分支指针均为NULL,则直接输出c,否则递归检查其是否为Contraction或Acronym,若是则替换,若不是依然直接输出c,继续检测下一字符。

    Source修正

    Alberta Collegiate Programming Contest 2003.10.18 – 问题D

    测试数据

    本文第二、第三页附带测试数据

    测试数据下载


    转载请注明:EXP 技术分享博客 » POJ2525 – Text Formalization

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址