二、Sandy 的卡片
(card.pas/c/cpp， 限时1 秒，内存256M)
【题目描述】
Sandy 和Sue 的热衷于收集干脆面中的卡片。
然而，Sue 收集卡片是因为卡片上漂亮的人物形象，而Sandy 则是为了积攒卡片兑
换超炫的人物模型。
每一张卡片都由一些数字进行标记，第i 张卡片的序列长度为Mi，要想兑换人物模
型，首先必须要集够N 张卡片，对于这N 张卡片，如果他们都有一个相同的子串长度为
k，则可以兑换一个等级为k 的人物模型。相同的定义为：两个子串长度相同且一个串
的全部元素加上一个数就会变成另一个串。
Sandy 的卡片数远远小于要求的N，于是Sue 决定在Sandy 的生日将自己的卡片送给
Sandy，在Sue 的帮助下，Sandy 终于集够了N 张卡片，但是，Sandy 并不清楚他可以兑
换到哪个等级的人物模型，现在，请你帮助Sandy 和Sue，看看他们最高能够得到哪个
等级的人物模型。
【输入文件】
第一行为一个数N，表示可以兑换人物模型最少需要的卡片数，即Sandy 现在有的
卡片数
第i+1 行到第i+N 行每行第一个数为第i 张卡片序列的长度Mi，之后j+1 到j+1+Mi
个数，用空格分隔，分别表示序列中的第j 个数
【输出文件】
一个数k，表示可以获得的最高等级。
【样例】
输入样例：
2
2 1 2
3 4 5 9
输出样例：
2
【数据范围】
30%的数据保证n<=50
100%的数据保证n<=1000
100%的数据保证m[i]<=101
山东省选08年第二轮第一天试题
后缀数组求解
最小的当然是1了
将序列上两项之间的差为内容生成后缀数组
两个各不同序列之间用-maxlongint的来分隔
之后二分答案
按二分的答案将后缀分组
若一组中出现了所有的序列，则该答案成立
测试数据
http://mail.qq.com/cgi-bin/ftnExs_download?k=773535621076cf9e6412407d1a31044e000505520501014e1e530655565550020718540004041c550651054f540653041c070207055509540357055050313961525447061b4350133173&t=exs_ftn_download&code=155b511a
program card;
var
n,i,j,k,tot,m,max,all,s,e,mid,temp,last:longint;
dl,root,belong:array [0..110001] of longint;
change,total,rank,sa,now,keep,height:array [-1..110001] of longint;
yes:array [0..1001] of boolean;
xl:array [0..1001] of longint;
ok:boolean;
function search (mid:longint):boolean;
begin
if mid=0 then exit(true);
fillchar(yes,sizeof(yes),false);
k:=1;
yes[belong[sa[n+1]]]:=true;
all:=1;
xl[1]:=belong[sa[n+1]];
for i:=n+2 to tot do
begin
if height[i]<mid then
begin
while all<>0 do
begin
yes[xl[all]]:=false;
dec(all);
end;
all:=1;
xl[1]:=belong[sa[i]];
yes[belong[sa[i]]]:=true;
k:=1;
continue;
end;
if not yes[belong[sa[i]]] then
begin
yes[belong[sa[i]]]:=true;
inc(all);
xl[all]:=belong[sa[i]];
inc(k);
end;
if k=n then exit(true);
end;
exit(false);
end;
procedure swap (var a,b:longint);
var
i:longint;
begin
i:=a;
a:=b;
b:=i;
end;
procedure qsort (s,e:longint);
var
i,j,k:longint;
begin
if s>=e then exit;
i:=s;
j:=e;
k:=dl[(s+e) div 2];
while i<=j do
begin
while root[dl[i]]<root[k] do inc(i);
while root[dl[j]]>root[k] do dec(j);
if i>j then break;
swap(dl[i],dl[j]);
inc(i);
dec(j);
end;
qsort(s,j);
qsort(i,e);
end;
begin
assign(input,'card.in');
reset(input);
assign(output,'card.out');
rewrite(output);
read(n);
max:=maxlongint;
tot:=0;
for i:=1 to n do
begin
read(m);
if m<max then max:=m;
if m<>0 then read(last);
for j:=tot + 1 to tot+m-1 do
begin
read(temp);
root[j]:=temp-last;
last:=temp;
belong[j]:=i;
end;
tot:=tot+m;
root[tot]:=-maxlongint;
end;
for i:=1 to tot do
dl[i]:=i;
qsort(1,tot);
k:=1;
for i:=1 to tot do
begin
if root[dl[i]]<>root[dl[k]] then k:=i;
rank[dl[i]]:=k;
end;
k:=0;
while 1 shl k<tot do
begin
for i:=1 to tot do
if i+(1 shl k)>tot then change[i]:=0
else change[i]:=rank[i+(1 shl k)];
fillchar(total,sizeof(total),0);
for i:=1 to tot do
inc(total[change[i]]);
for i:=1 to tot do
total[i]:=total[i]+total[i-1];
for i:=1 to tot do
begin
inc(total[change[i]-1]);
dl[total[change[i]-1]]:=i;
end;
fillchar(total,sizeof(total),0);
ok:=true;
for i:=1 to tot do
begin
inc(total[rank[i]]);
if total[rank[i]]=2 then ok:=false;
end;
if ok then break;
for i:=2 to tot do
total[i]:=total[i]+total[i-1];
fillchar(now,sizeof(now),0);
fillchar(keep,sizeof(keep),0);
for i:=1 to tot do
begin
if now[rank[dl[i]]]<>change[dl[i]] then
begin
now[rank[dl[i]]]:=change[dl[i]];
total[rank[dl[i]]-1]:=total[rank[dl[i]]-1]+keep[rank[dl[i]]];
keep[rank[dl[i]]]:=0;
end;
inc(keep[rank[dl[i]]]);
rank[dl[i]]:=total[rank[dl[i]]-1]+1;
end;
inc(k);
end;
for i:=1 to tot do
sa[rank[i]]:=i;
fillchar(height,sizeof(height),0);
for i:=1 to tot do
begin
if rank[i]=1 then continue;
k:=height[rank[i-1]]-1;
if k<0 then k:=0;
while (i+k<=tot)and(sa[rank[i]-1]+k<=tot)
and(root[i+k]=root[sa[rank[i]-1]+k]) do inc(k);
height[rank[i]]:=k;
end;
if max<=1 then
begin
writeln(max);
close(input);
close(output);
exit;
end;
s:=1;
e:=max;
while s<>e do
begin
mid:=s+e-(s+e) div 2;
if search(mid-1) then s:=mid
else e:=mid-1;
end;
writeln(s);
close(input);
close(output);
end.