POJ 1226(最长公共子串含逆序）

Substrings
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 9639   Accepted: 3319
Description
请找出一些串的最长‘正/逆‘子串，使它为所有的串的子串（即使是逆序也认为包含）.
Input
第一行为数据数t，(1 <= t <= 10),
对每组数据而言:第一行为字符串个数 n (1 <= n <= 100)，接下来n行为字符串（长度不超过100） .
Output
每行一个数，表示最长'正/逆‘子串的长度。
Sample Input
2
3
ABCD
BCDFF
BRCD
2
rose
orchid
Sample Output
2
2
Source
Tehran 2002 Preliminary
还是KMP，先在第一个串中枚举串，之后考察它是否是其它串的'正/逆'子串。

[delphi] 
Program P1226; 
const 
   maxn=100; 
   maxt=10; 
var 
   tt,n,m,i,j,k,ans:longint; 
   flag:boolean; 
   a:array[1..maxn] of string; 
   p:string; 
   next:array[1..maxn] of longint; 
 
function kmp(a,b:string):boolean; 
var 
   i,j,n,m:longint; 
begin 
   i:=1;j:=0;next[1]:=0; 
   n:=length(a); m:=length(b); 
   while (i<m) do 
   begin 
      if (j=0) or (b[i]=b[j]) then 
      begin 
         inc(i);inc(j); 
         if (b[i]<>b[j]) then next[i]:=j else next[i]:=next[j]; 
      end else j:=next[j]; 
   end; 
 
   i:=0;j:=0; 
   while (i<=n) and (j<=m) do 
   begin 
      if (j=0) or (a[i]=b[j]) then 
      begin 
         inc(i);inc(j); 
      end else j:=next[j]; 
   end; 
   if (j>m) then exit(true); 
   exit(false); 
end; 
function ob_s(a:string):string; 
var 
   i,j,n:longint; 
begin 
 
   ob_s:=''; n:=length(a); 
   for i:=n downto 1 do ob_s:=ob_s+a[i]; 
end; 
function compare(a,b:string):boolean; 
var 
   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(a[i]<b[i]); 
   exit(false); 
end; 
 
 
begin 
   readln(tt); 
   while (tt>0) do 
   begin 
      ans:=0; 
      readln(n); 
      for i:=1 to n do readln(a[i]); 
 
      for i:=1 to length(a[1]) do 
         for j:=i to length(a[1]) do 
         begin 
            p:=copy(a[1],i,j-i+1); 
            flag:=true; 
            for k:=2 to n do 
            begin 
               if not((kmp(a[k],p) or kmp(a[k],ob_s(p)))) then 
               begin 
                  flag:=false; break; 
               end;  www.2cto.com
            end; 
            if flag and (length(p)>ans) then ans:=length(p); 
 
 
         end; 
 
      writeln(ans); 
      dec(tt); 
   end; 
end.