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

    ACM-POJ EXP 227阅读 0评论

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


    大致题意

    就是求k个长度为60的字符串的最长连续公共子串,2<=k<=10

    规定:

    1、 最长公共串长度小于3不输出

    2、 若出现等长的最长的子串,则输出字典序最小的串

    解题思路

    LCS问题,纠结了几个月放着没做的题目。。

    一直以为要用KMP或者后缀数组来做。。。

    然后我就拼命学后缀。。。

    今天偶然发现直接 暴力 能够达到0ms的效果= =

    所以。。。暴力吧。。。不愧为初级的题。。。


    暴力思想很简单:

    开二维DNA[][]保存所有DNA序列

    1、 以DNA[0]为母版,顺次截取60个长度length=1的子串dna[],检查其他DNA[i]是否都有子串dna,若是则把dna[]复制到obj[],否则枚举下一个长度length的子串;若obj与新的dna等长,则比较两者字典序,当dna字典序小时,复制到obj

    2、 第1步循环60次后length+1。

      顺次截取59个长度length=2的子串dna[],重复1的操作更新obj。。

    3、 第2步循环59次后length+1。

      顺次截取58个长度length=3的子串dna[],继续。。

    ………..

    60、第59步循环2次后length+1。

      顺次截取1个长度length=60的子串dna[],继续重复操作更新obj。。

    61、输出obj


    Source修正

    2006 South Central USA Regional Programming Contest (问题4)

    测试数据

    本文第二页附带测试数据

    测试数据下载

    转载请注明:EXP 技术分享博客 » POJ3080 – Blue Jeans

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

    表情

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

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