POJ 3080 Blue Jeans

表示今天下午ac了一道放置几天的问题，开心=。=

Description

Input

Output

Sample Input

3
2
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
3
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
3
CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

Sample Output

no significant commonalities
AGATAC
CATCATCAT

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
	int nn,cc;
	cin>>nn;
	for(cc=1;cc<=nn;cc++)
	{
		int n;
		cin>>n;
		char a[20][65];
		int i,j;
		for(i=0;i<n;i++)
			cin>>a[i];
		char str[65];
		char s[65];
		int sum=0,max=0;
		int len=0;
		int maxlen=0;
		for(i=0;i<61;i++)
		{
			for(j=i+3;j<61;j++)
			{
				int k;
				bool flag=1;
				int m1=i;
				for(k=0;k<j-i;k++)
				{
					str[k]=a[0][m1];
					m1++;
					if(m1==j)
						break;
				}
				str[k+1]='\0';
				int m;
				for( m=1;m<n;m++)
					if(strstr(a[m],str)==NULL)
						flag=0;
					if(flag)
					{
						len=j-i; 
						if(len>maxlen)
						{
							maxlen=len;
							strcpy(s,str);
						}
						else if(len==maxlen)  
						{  
							if(strcmp(s,str)>0)  //存在相同长度的公共串时，取最小字典序的串  
								strcpy(s,str);  
						}  
					}
					
			}
		}
		if(maxlen<3)
			cout<<"no significant commonalities"<<endl;
		else
			cout<<s<<endl;
	}
	
	return 0;
}


/*
3
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
*/
/*
2
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
2
GATGATGCATCATGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGACTACTAA
GATGATCATCATACTACTCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
*/

POJ 3080 Blue Jeans,布布扣,bubuko.com

POJ 3080 Blue Jeans

原文：http://blog.csdn.net/sunshumin/article/details/37992085