3080 Blue Jeans

問題概要

60文字のG,A,T,Cからなる塩基配列がn個与えられる。
n個全てに共通する連続する塩基配列で、最も長いものを求めよ。
複数ある場合はアルファベット順で最も最初に来るものを求めよ。

n≦10を満たす。

解法

サイズが小さいので特別なマッチングのアルゴリズムなどは不要。
部分文字列を全通り試す。

といってもサイズが大きい場合はどう工夫するんだろう。
マッチングにKMPなどを使うくらいの改良しか思い浮かばない。

ソースコード

string in[10];
int main()
{
	int n,T; cin>>T;
	rep(U,T){
		cin>>n; cin.ignore();
		rep(i,n)getline(cin,in[i]);
		for(int w=60;w>=3;w--){
			string ans;
			rep(l,61-w){
				string ptn=in[0].substr(l,w);
				for(int i=1;i<n;i++)if(in[i].find(ptn)==string::npos)goto FAIL;
				if(ans.empty()||ptn<ans)ans=ptn;
				FAIL:;
			}
			if(!ans.empty()){
				puts(ans.c_str()); goto END;
			}
		}
		puts("no significant commonalities"); END:;
	}
	return 0;
}