加载中...

POJ 3080 - Blue Jeans


问题描述

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

规定:

  • 最长公共串长度小于3不输出
  • 若出现等长的最长的子串,则输出字典序最小的串

解题思路

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

测试数据

AC 源码

//Memory Time 
//248K   16MS 

#include<iostream>
#include<string.h>
using namespace std;

const int len=60;

int main(int i,int j)
{
    int test;
    cin>>test;
    for(int t=1;t<=test;t++)
    {
        int n;  //DNA个数
        cin>>n;
        char** DNA=new char*[n];
        for(int p=0;p<n;p++)
        {
            DNA[p]=new char[len+1];
            cin>>DNA[p];
        }

        char obj[len+1];  //所有DNA的公共串
        int StrLen=0;    //最长公共串长度
        int length=1;    //当前枚举的公共串长度

        for(i=0;;i++)  //枚举公共串dna[]
        {
            /*截取DNA[0][]中以pi为起点,长度为length的子串dna[]*/
            char dna[len+1];
            int pi=i;
            if(pi+length>len)
            {
                length++;
                i=-1;
                if(length>len)
                    break;
                continue;
            }
            for(j=0;j<length;j++)
                dna[j]=DNA[0][pi++];
            dna[j]='\0';

            /*检查其他DNA[][]是否都存在字符串dna[]*/
            bool flag=true;
            for(int k=1;k<n;k++)
                if(!strstr(DNA[k],dna))  //存在一个DNA不含有dna[]
                {
                    flag=false;
                    break;
                }

            /*确认最大公共串*/
            if(flag)
            {
                if(StrLen<length)
                {
                    StrLen=length;
                    strcpy(obj,dna);    
                }
                else if(StrLen==length)
                {
                    if(strcmp(obj,dna)>0)  //存在相同长度的公共串时,取最小字典序的串
                        strcpy(obj,dna);
                }
            }
        }

        if(StrLen<3)
            cout<<"no significant commonalities"<<endl;
        else
            cout<<obj<<endl;

        delete DNA;
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
  目录