var
  i,j,n,m,k,ans,max,p,t:longint;
  a,d,height,tsa,sa,rank,x,y:array[-10..100000]of longint;
  sum:array[0..500]of longint;
procedure suffix;
begin
  for i:=1 to n do inc(sum[a[i]]);
  for i:=1 to 500 do sum[i]:=sum[i-1]+sum[i];
  for i:=n downto 1 do
    begin
      sa[sum[a[i]]]:=i;
      dec(sum[a[i]]);
    end;
  p:=0;
  for i:=1 to n do
    begin
      if a[sa[i]]<>a[sa[i-1]] then inc(p);
      rank[sa[i]]:=p;
    end;
  j:=1;
  while p<n do
    begin
      for i:=1 to n do
        begin
          x[i]:=rank[i];
          y[i]:=rank[i+j];
        end;
      fillchar(sum,sizeof(sum),0);
      for i:=1 to n do inc(sum[y[i]]);
      for i:=1 to 500 do sum[i]:=sum[i-1]+sum[i];
      for i:=n downto 1 do
        begin
          tsa[sum[y[i]]]:=i;
          dec(sum[y[i]]);
        end;
      p:=0;
      for i:=1 to n do
        begin
          if y[tsa[i]]<>y[tsa[i-1]] then inc(p);
          rank[tsa[i]]:=i;
        end;

      fillchar(sum,sizeof(sum),0);
      for i:=1 to n do inc(sum[x[tsa[i]]]);
      for i:=1 to 500 do sum[i]:=sum[i-1]+sum[i];
      for i:=n downto 1 do
        begin
          sa[sum[x[tsa[i]]]]:=tsa[i];
          dec(sum[x[tsa[i]]]);
        end;
      p:=0;
      for i:=1 to n do
        begin
          if (x[sa[i]]<>x[sa[i-1]])or(y[sa[i]]<>y[sa[i-1]]) then inc(p);
          rank[sa[i]]:=p;
        end;
      j:=j shl 1;                            
    end;
end;
function check(k:longint):boolean;
var max,min:longint;
begin
  max:=0;
  min:=maxlongint;
  for i:=2 to n do
    begin
      if height[i]>=k-1 then
        begin
          if sa[i]>max then max:=sa[i];
          if sa[i]<min then min:=sa[i];
          if max-min>=k then exit(true);
        end else
      begin
        max:=sa[i];
        min:=sa[i];
      end;
    end;
  exit(false);
end;
procedure work(l,r:longint);
var mid:longint;
begin
  if l>r then exit;
  mid:=(l+r)shr 1;
  if check(mid) then
    begin
      if mid>ans then ans:=mid;
      work(mid+1,r);
    end else work(l,mid-1);
end;
procedure Get_Height;
begin
  for i:=1 to n do
    begin
      k:=0;
      while (sa[i]+k<=n)and(sa[i-1]+k<=n)and(a[sa[i]+k]=a[sa[i-1]+k]) do inc(k);
      height[i]:=k;
    end;
end;
procedure init;
begin
  readln(n);
  while n<>0 do
    begin
      ans:=0;
      fillchar(sum,sizeof(sum),0);
      for i:=1 to n do
        read(d[i]);
      d[0]:=-1;
      for i:=1 to n do
        a[i]:=d[i]-d[i-1];
      for i:=1 to n do a[i]:=a[i]+200;
      suffix;
      Get_Height;
      work(1,n);
      writeln(ans);
      readln(n);
    end;
end;
begin
  init;
end.

• Re:整个人崩溃掉了！！一直RE是怎么回事啊~求救啊想自杀了。。 (2696) strawberryfouge 2012-01-08 09:27:57
  • Re:整个人崩溃掉了！！一直RE是怎么回事啊~求救啊想自杀了。。 (23) strawberryfouge 2012-01-08 09:29:08