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.
