POJ3080-Blue Jeans

[POJ] [INDEX] [3080] [Blue Jeans]

[Time: 1000MS] [Memory: 65536K] [难度: 初级] [分类: 串]

---

问题描述

就是求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

测试数据

• 来源：2006 South Central USA Regional Programming Contest （问题4）
• 下载：download
• 输入：input
• 输出：output

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;
}

---

版权声明

　　

• Site: http://exp-blog.com
• Mail: [email protected]

---