POJ 3080(最长公共子串）

Posted on by
内容目录
Language:
Blue Jeans
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 8767   Accepted: 3688

Description

给出若干个基因串（由'A','T','S','C'构成），请找出最长公共子串。

Input

第一行为数据数。
对每组数据：第一行为字符串的个数m(2 <= m <= 10)
                        之后m行，每行一个基因串（有且仅有60个字母）

Output

对每组数据，找出最长公共子串，如果长度小于3，请输出 "no significant commonalities" ，否则输出最长的字符串，若有多个答案，输出字典序最小的。

Sample Input

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

Sample Output

no significant commonalities
AGATAC
CATCATCAT

Source

South Central USA 2006

枚举字符串更新答案，用kmp算法进行匹配。


Program BlueJeans;
const
   maxn=60;
   maxm=10;
var
   tt,i,j,k,n,m:longint;
   a:array[1..maxm] of string;
   next:array[1..maxn] of longint;
   p,ans:string;
   flag:boolean;

function kmp(a,s:string):boolean;
var
   i,j,n:longint;
begin
   n:=length(a);

   j:=0; next[1]:=0; i:=1;
   while i<n do
   begin
      if (j=0) or (a[i]=a[j]) then
      begin
         inc(i); inc(j);
         if (a[i]<>a[j]) then next[i]:=j else next[i]:=next[j];
      end else j:=next[j];
   end;

   j:=0; i:=0;
   while (i<=maxn) and (j<=n) do
   begin
      if (j=0) or (a[j]=s[i]) then
      begin
         inc(i); inc(j);
  //       if (j=n) then exit(true);
      end else j:=next[j];
   end;

   if j>n then exit(true);
   exit(false);


end;
function compare(a,b:string):boolean;
var
   i,n,m:longint;
begin
   n:=length(a); m:=length(b);
   if (n<>m) then exit(n<m);
   for i:=1 to n do if (a[i]<>b[i]) then exit(ord(a[i])>ord(b[i]));
   exit(false);
end;
begin
   readln(tt);
   while (tt>0) do
   begin
      ans:='';
      readln(m);
      for i:=1 to m do readln(a[i]);

      for i:=1 to maxn do
         for j:=i to maxn do
         begin
            p:=copy(a[1],i,j-i+1);
            flag:=false;
            for k:=2 to m do
            begin
               if not(kmp(p,a[k])) then begin flag:=true; break; end;
            end;
            if not(flag) and (compare(ans,p)) then ans:=p;
         end;

      if length(ans)<3 then writeln('no significant commonalities')
      else writeln(ans);




      dec(tt);
   end;
end.